RSA 学习记录

A向B广播一条消息：B，我有要事汇报

B立即生成两个大素数，p,q 算出n=p*q 并取一个素数 e=65537 广播 n,e 即加密密钥

A收到了n,e 攻击者也收到了n,e

A立即将情报通过hex和padding 转换成一串数字 m 算m^e mod n = c 即 c = pow(m,e,n)

此时 A手上有 n,e,m,c 想把c传给B

广播通信出去 B 收到了c 攻击者收到了c

目前 A 有 n,e,m,c B 有 p,q,n,e,c

攻击者 有 n,e,c

B 比攻击者多了 p,q 计算e关于n的欧拉函数的逆元 即 ed = 1 mod (n) (n) 是 n 的欧拉函数 即 (n) = (p-1)(q-1)

可通过扩展的欧几里得算法求出d

import primefac d = primefac.modinv ( e , (p-1) * (q-1) ) % ( (p-1) * (q-1) )

B 又多了个d 可算出 m = c^d mod n 即 m = pow(c,d,n) B 最终得到m 是 A 发过来的情报

因为攻击者没有 p,q 就不能算出 d 也就不能解密 c 得到 m

d, n 为此密码的私钥

我画个流程图好理解点 使用openssl 读取pem 文件中的信息 查看公钥文件

openssl rsa -pubin -in pubkey.pem -text -modulus

解密结果如下

rsautl -decrypt -inkey private.pem -in flag.enc -out flag

本文读完需要5分钟

直接模数分解费马分解Pollard_rho分解公约数模数分解

直接模数分解

2048bit的n 是安全的 通常小于256b 模数分解 pycrypto-2.6.1/ PyCrypto中提供了用于生成大素数、素性检测等的函数

from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime,isPrime print isPrime(getPrime(1024))

输出 1

from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime,isPrime p=getPrime(128) q=getPrime(128) n=p*q print p print q print n

输出

264557343544462264095085670795796368069 254600537743868350285359152454615998047 67356441930509410513140786204783020450831743401635998443649164089866197161243

示例yafu分解 例题1、 假如题目只给了公钥，我们要获取明文 我们只有 n,e,c 为了计算d 从而解出c 首先要把n分解

n=41376961156168948196303384218941117367850019509202049026037168194982219784159 e=65537 c=4161293100530874836836422603625206824589693933040432789074054165274087272587

得到

p=130451115685568383270871808144053983073 q=317183651045971246384245233153006206783 from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime,isPrime import primefac def modinv(a,n): return primefac.modinv(a,n) % n n=41376961156168948196303384218941117367850019509202049026037168194982219784159 e=65537 c=4161293100530874836836422603625206824589693933040432789074054165274087272587 p=130451115685568383270871808144053983073 q=317183651045971246384245233153006206783 d=modinv(e,(p-1)*(q-1)) m=pow(c,d,n) print long_to_bytes(m) //m转换成字符串

输出

费马分解

直接分解n成功的原因是两个素数太小，导致直接爆破 p,q都是素数也是奇数， 存在 a=(p+q)/2,b=(p-q)/2 n=a^ 2 - b^2 即通过枚举大于n的完全平方数 就可以分解n 这种方法适用于p,q差距很小的情况 因为（p-q）/ 2 的值就很小

Pollard_rho分解

通过某种方法得到两个整数a,b 计算 p = gcd ( a-b,n ) 最大公约数 直到p不为1 或者a,b 出现循环为止

判断p==n ？n是质数：p是n的一个因子

递归计算Pollard§ 和Pollard(n/p) 求出n的所有质因子

使用函数 X2 = X1^2+c 计算a，b 通常取c=1 即 b=a^2+1 然后把b的值赋给a 再求出新的b 直到 a,b 出现循环

这种方法适用于p或q其中一方过小 即p,q差距大

公约数模数分解

如果A和B进行两次通信 B两次产生的p,q 有一个假设p出现了两次 那么攻击者可以通过最大公约数计算n1,n2共同的因子p 通过除p 分解n1,n2

题目给出n1 n2 c1 c2 e1 e2 求n1 n2的最大公约数 得到p1==p2 再求q1 q2 得到d1 d2 由 c d n 得到 m1 m2

p1=primefac.gcd(n1,n2) p2=p1 q1=n1/p1 q2=n2/p2 e1=65537 e2=65537 d1=modinv(e1,(p1-1)*(q1-1)) d2=modinv(e2,(p2-1)*(q2-1)) m1=pow(c1,d1,n1) m2=pow(c2,d2,n2) print long_to_bytes(m1) print long_to_bytes(m2)