美文网首页
RSA算法及Fault Injection攻击数学原理

RSA算法及Fault Injection攻击数学原理

作者: 苏里南公牛 | 来源:发表于2020-02-13 12:07 被阅读0次

    what

    RSA算法是什么以及实现原理,这个不需要我也轮不到我来讲,比较深入浅出的是阮一峰的两篇《RSA算法原理》博客,大家去谷他一歌即可。本文需要读者了解非对称加密的概念

    本文提到RSA算法主要是为了讲Fault Injection(以下简称FI)攻击的数学原理,而讲解FI的数学原理又必须要牵涉到RSA算法的数学原理。实际上,FI攻击不仅可以针对RSA加密算法,也可以针对其他加密算法,不过RSA加密算法的数学原理相对容易理解,相应的FI攻击的数学原理也相对容易理解,所以挑选RSA算法及其对应的FI攻击原理来展开本文。

    作为一篇马桶上读物,本文不会牵涉到艰深晦涩的数学公式推导及证明,因为主要一方面是我不会,另一方面本人自从若干年前丧失数学能力之后,一直对那些满篇数学公式猛推如虎的文章深恶痛绝,感到智商受到万吨伤害之余也忍不住想骂一句《大话西游》里的台词:”一天到晚就知道哦哦哦,完全不管人家受得了受不了“。

    因此本文不可避免会牵涉一定的数学公式,但我保证都是高中数学范畴,且会用最通俗化的语言解释what、how以及why。

    how

    假设有两人S(sender)以及R(receiver),S想要通过RSA算法来加密自己的信息发送给R,具体应该怎么做呢?

    对于R来说(注意,这里是接收者的公钥及私钥计算过程,而不是想当然的发送者的公钥及私钥计算过程):

    · 第一步,随机选择两个不相等的质数p和q。

    假设R选择了61和53,则:

    p = 61

    q = 53

    · 第二步,计算p和q的乘积。

    n = p * q = 61 * 53 = 3233

    · 第三步,计算n的欧拉函数φ(n)。

    欧拉函数的概念:

    任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

    计算这个值的方法就叫做欧拉函数,以φ(n)表示。

    欧拉函数有如下性质:

    1. 如果n是质数,则φ(n) = n - 1

    2. 令n = p * q,则φ(n) = φ(p * q) = φ§ * φ(q)

    即,积的欧拉函数等于各个因子的欧拉函数之积。

    根据上面的性质,易知:

    φ(n) = φ(p * q) = φ(p) * φ(q) = (p - 1) * (q - 1)

    R算出来:

    φ(n) = 60 * 52 = 3120

    · 第四步,随机选择一个整数e,满足1 < e < φ(n),且e与φ(n)互质。

    假设R在1到3120之间,R随机选择了17,则:

    e = 17

    · 第五步,计算e对于φ(n)的模反元素d。

    什么是模反元素呢:

    如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。记作:

    ab ≡ 1 (mod n)

    b就叫做a的"模反元素"。

    上述概念中的数学公式,等价于计算机编程语言里的表示方法(好理解一些):

    ab % n = 1

    套用模反元素的概念可知,我们一定能找到一个整数d,使得ed被φ(n)除的余数为1,即:

    ed ≡ 1 (mod φ(n))

    该式等价于:

    ed - 1 = kφ(n)

    于是,找到模反元素d,实质上就是对下面这个二元一次方程求解:

    ex + φ(n)y = 1

    已知e = 17,φ(n) = 3120,代入上式:

    17x + 3120y = 1

    此方程可以用”扩展欧几里得算法“求解,此处省略具体求解过程。

    总之,R算出一组整数解为(x, y) = (2753, -15),即:

    d = 2753

    · 第六步,将n和e封装成公钥,n和d封装成私钥。

    我们的例子里,n = 3233,e = 17,d = 2753,因此公钥为(3233, 17),私钥为(3233, 2753)。其中,私钥中的d是公钥中的e对于φ(n)的模反元素。

    公钥是公开的密钥,也就是说,任何人(当然包括S发送者)都可以知道n和e的值;私钥是只有接收者R自己知道的密钥,也就是说,只有R自己知道d的值。

    对于攻击者来说,TA想探取的就是这个私钥,私钥里的n是已知的,剩下需要探取的就是这个d的值。

    至于RSA算法的可靠性,阮一峰的博客里有详细证明这里不再赘述。总之结论是,在已知n和e,且n和e的长度满足一定条件的前提下,是无法通过数学推导或在可观的时间内暴力破解出d的,因而保证了私钥的不可破解性。

    another how

    通过第二节,我们了解了RSA公钥及私钥运算过程,涉及到的数学公式、定理、概念经过去繁存简,也都是一目了然的。

    这一节讲解在获取到RSA算法的公钥及私钥后,如何利用公钥私钥体系来进行数据的加密及解密:

    · 加密要用公钥(n, e)

    假设S要向R发送加密信息m,S先用R的公钥(n, e)对m进行加密(这里注意m必须是整数,字符串可以取ASCII值或unicode值),且m必须小于n。

    所谓的“加密”,就是算出下面式子的c:

    R的公钥是(3233, 17),S的m假设是65,代入上式:

    于是,计算出的密文c等于2790,S就把2790发送给了R。

    注意,这里明文为m,也就是65;经过R的公钥加密后,密文c为2790。

    · 解密要用私钥(n, d)

    R拿到S发过来的2790(c,密文)后,用自己的私钥(3233, 2753)进行解密。可以证明,下式成立:

    也就是说,c的d次方除以n的余数为m(对n求余为m)。现在c等于2790,私钥是(3233, 2753),那么R算出:

    因此,R知道了S加密前的原文m就是65。

    以上就是RSA“加密-解密”的全过程。

    what’s Fault Injection

    Fault Injection攻击是啥呢,通俗地来说,就是将要攻击的目标(芯片、算法)看作是一个黑盒子,在能对黑盒内部的一些数据属性,进行一定程度的、可控的干涉影响的条件下,人为地构造一些错误,并通过观察这个黑盒在错误情况下的输出,来反推黑盒里的一些数据属性。

    当然这是我个人的理解及概括,肯定不严谨,而且我也不是这方面的专家,只是与高晓松他六叔聊天得知FI这一硬件攻击技术手段并阅读了一些文献,了解了一些皮毛。

    FI被证明是一个很有效的用于秘钥窃取的攻击手段,可以针对目前几乎所有的加密算法,包括AES,DES,RC4,RSA以及ECC。

    how FI works

    针对RSA的FI攻击,只能在解密阶段施展。

    易读性起见,这里再罗列上文提到的若干关键变量:

    p和q是随机挑选的一对不相等的质数。

    n = p * q

    e是随机挑选的,1 < e < φ(n),且e与φ(n)互质。

    d和e是一对关于φ(n)的模反元素。

    (n, d)为私钥,(n, e)为公钥。

    m为明文,c为密文

    我现在假设:

    1. 你手上已经有一块芯片,里面运行的是RSA解密算法。换句话说,此芯片内部一定包含解密所需的私钥(n,

    d)。现在攻击的目标,就是探取私钥(n, d)中的d(n属于公钥的一部分,是已知的)。

    2. 通过一定的手段,你可以翻转d中的任意一个bit位。换句话说,你做下一个手脚后(激光照射、降频降压、火烧电击,whatever),会使得如果d中的某一个bit原来为0,在做完手脚后这个bit会变为1;反之亦然。当然你是不知道d的任意一个bit位原来到底是0还是1,但是你有手段可以使其发生翻转。

    3. 对于每一组输入的密文,通过这颗芯片的运算(RSA解密算法黑盒),你总是可以捕获到它的输出。

    再把前文描述到的RSA解密过程所需的公式写在下面:

    上式等价于:

    对于每组输入的密文c,解密芯片中的算法,总是能通过自己的私钥d,算出原文m。

    关键的部分到了,下面是FI数学原理的分析过程:

    · 假设d的第i个bit位原来为0,那么在做了一次手脚后,该位会被翻转成1,翻转后的d值记为(d撇):

    易知,此情况下:

    此情况下,对于输入密文c(此密文攻击者可以自己构造),记c在秘钥d被篡改成d撇后的解密输出为m撇:

    则有:

    m、m撇可以通过捕获输出得知,c、i是攻击者构造的,n已知。

    · 假设d的第i个bit位原来为1,那么在做了一次手脚后,该位会被翻转成0。

    易知,此情况下:

    同理易得:

    也就是说:在相同的密文c输入下,可以观察,分别在d和d撇的情况下,解密输出的m和m撇的比值到底是

    还是

    来反推d的第i位原来到底是0还是1。

    如果对d的每一个bit位都尝试做一次手脚,就可以探知d的值。

    这里还可以通过翻转c的若干bit位施展攻击,具体不再详述。

    summary

    从RSA的算法构造,到FI攻击反窥私钥,无处不是数学。

    在感叹构思出这些方法之人(无论是攻还是防)的智慧之余,无不惋惜自己数学能力的低下,大概也只能做个码农。

    本文是我的一点粗略心得,起抛砖引玉之功效,纰漏之处在所难免,恭请斧正。

    另,文末附上一段我之前用python写的玩具级别的RSA算法实现,包括了公钥、私钥生成及加解密过程,可以起一窥算法流程关节之作用,感兴趣的话可以取食。

    #!/usr/bin/python

    class rsa:

      def __init__(self, p, q):

          self.p = p;

          self.q = q;

      def __get_list__(self):

          e_list = []

          for n in range(2, self.phi):

              if self.__gcd__(self.phi, n) == 1:

                  e_list.append(n)

          return e_list

      def __extend_Eulid__(self):

          def __get_args_list__(x, y):

              # assume x > y

              if y == 0:

                  return x

              t = x / y

              m = x % y

              self.x_list.append(x)

              self.xt_list.append(1)

              self.y_list.append(y)

              self.yt_list.append(t)

              self.m_list.append(m)

              return __get_args_list__(y, m)

          __get_args_list__(self.phi, self.e)

          self.x_list.pop()

          self.xt_list.pop()

          self.y_list.pop()

          self.yt_list.pop()

          self.m_list.pop()

          for i in range(0, len(self.yt_list)):

              self.yt_list[i] = -self.yt_list[i]

          self.m_list.reverse()

          self.x_list.reverse()

          self.xt_list.reverse()

          self.y_list.reverse()

          self.yt_list.reverse()

          m = self.m_list[0]

          x = self.x_list[0]

          xt = self.xt_list[0]

          y = self.y_list[0]

          yt = self.yt_list[0]

          # x always greater than y

          for i in range(1, len(self.m_list)):

              tmp_yt = yt

              tmp_xt = xt

              x = self.x_list[i]

              xt = self.xt_list[i] * tmp_yt

              y = self.y_list[i]

              yt = tmp_xt + self.yt_list[i] * tmp_yt

          return yt % self.phi

      def __gcd__(self, x, y):

          # assume x > y

          if y == 0:

              return x

          return self.__gcd__(y, x % y)

      def gen_key( self ):

          self.x_list = []

          self.xt_list = []

          self.y_list = []

          self.yt_list = []

          self.m_list = []

          self.n = p * q

          self.phi = (p - 1) * (q - 1)

          self.e = int(raw_input("input e " + str(self.__get_list__()) + ": "))

          self.d = self.__extend_Eulid__()

      def encode(self, m):

          return m ** self.e % self.n

      def dncode(self, c):

          return c ** self.d % self.n

    if __name__ == "__main__":

      p = int(raw_input("input p: "))

      q = int(raw_input("input q: "))

      ins_rsa = rsa(p = p, q = q)

      ins_rsa.gen_key()

      while True:

          m = int(raw_input("input m:"))

          c = ins_rsa.encode(m)

          print c

          m = ins_rsa.dncode(c)

          print m

    相关文章

      网友评论

          本文标题:RSA算法及Fault Injection攻击数学原理

          本文链接:https://www.haomeiwen.com/subject/uhpkfhtx.html