RSA是怎么杀死我的 Surager

RSA——第一次不自闭

理论

基础知识

  • 互质

    互质就是两个数的最大公约数是1,gcd(a,b)=1

    任意两个质数都互质

  • 同余

    给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,那么就称整数a与b对模m同余,记作$a≡b(mod\ m)$ 其实可以这么理解:a对m取余后得到b:$a\ mod\ m=b$

  • 欧拉函数

    对正整数n,欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目

    欧拉函数是积性函数,若m,n互质,则 $φ(mn)=φ(m)φ(n)$ 若n为质数,则 $φ(n)=n-1$

  • 模反元素

    如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。这时,b就叫做a对模数n的“模反元素” 。

    即 $ab≡1 (mod\ n)$ 也可以这么理解:ab对n取余之后得到1,b就是a的模反元素$ab\ mod\ n = 1$

    各种定理和算法

  • 欧拉定理

    若n,a为正整数,且n,a互质,则 $a^{φ(n)}=1\ (mod\ n)$

  • 欧几里得算法

    是求最大公约数的一种方法。

    用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

    代码实现:

    def gcd(a,b):
        if b==0:
            return a
        else:
            return gcd(b,a%b)
    
  • extend_gcd

    如果a、b是整数,那么一定存在整数x、y使得:$ax+by=gcd(a,b)$ 这是一个很简单的问题,但是解决它就⑧一定简单了

    这时候就要用到extend_gcd算法だよ。

    1. 显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
    2. ab!=0 时, $ax~1~+by~1~=gcd(a,b);$ $bx~2~+(a mod b)y~2~=gcd(b,a mod b);$
    3. 根据朴素的欧几里德原理有$ gcd(a,b)=gcd(b,a mod b)$;则:$ax~1~+by~1~=bx~2~+(a mod b)y~2~$;
    4. 即:$ax~1~+by~1~=bx~2~+(a-(a/b)b)y~2~=ay~2~+bx~2~-(a/b)by~2~$;
    5. 根据恒等定理得:$x~1~=y~2~; y~1~=x~2~-(a/b)*y~2~; $

    上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

    所以代码实现:

    def egcd(a,b):
        if b == 0:
            return 1,0,a
        else:
            x,y,q = egcd(b,a % b)
            return y,x-a/b*y,q
    
  • 孙子定理(中国剩余定理)

    学习的事以后再说——老总

实践

加密过程

  1. 随机选两个不相等的质数p和q。

    例如:p=14214677

    ​ q=15733001

  2. 两数相乘得到n

    $n=p*q=22363952745677$

  3. 将两数分别减一再相乘得到phin

    $phin=(p-1)(q-1)=223639497508000$

  4. 随机选择一个整数 e ( 1 < e < phin 且 e 与 phin 互质) e=65537

  5. 计算e对于phin的模反元素。

    $ed≡1\ (\ mod\ φ(n))$ 得到d=156179448585473

  6. n和e组成公钥,n和d组成私钥。 公钥(22363952745677,65537) 私钥(22363952745677,156179448585473)

公钥加密

加密flag

m=int('flag'.encode('hex'),16)

$m^e≡c\ (mod\ n)$

python中可操作:pow(m,e,n)

得到c=32176455243891

私钥解密

$c^d≡m\ (mod\ n)$

题目分析

RSA_small_plain

小公钥指数攻击,e=7还⑧算大

因为 $c≡m^e(mod n)$ 然后可以设 $m\^e=c+kn,m=(c+kn)\^{1/e}$ 然后扯淡的是,直接给c开7次方,是个整数……

image-20191123224916451

直接decode:

image-20191123225159836

RSA_common_modulus

有n,和e1,e2,c1,c2

应该是共模攻击s1e1+s2e2=1

扩展欧几里得算法求一波s1和s2

image-20191129230154194

然后发现s2是个负的,就求c2r取-s2次方

image-20191129232338217

最后解码

image-20191129232413702