RSA

2018-06-09  本文已影响0人  Lou00

了解概念

相关资料https://www.kancloud.cn/kancloud/rsa_algorithm/48493

P : 大质数
Q : 大质数
N(Modulus) : N=P*Q
C : 密文
M : 明文
C=ME mod N(加密过程)
M=CD mod N(解密过程)
公钥(E , N) 私钥(D , N) 密钥对(E , D , N)

同余定理

给定一个正整数m,如果两个整数a和b满足(a-b)能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。
性质: 1 反身性 a≡a (mod m)
2 对称性 若a≡b(mod m),则b≡a (mod m)
3 传递性 若a≡b (mod m),b≡c (mod m),则a≡c (mod m)
4 同余式相加 若a≡b (mod m),c≡d(mod m),则a+-c≡b+-d (mod m)
5 同余式相乘 若a≡b (mod m),c≡d(mod m),则ac≡bd (mod m)

欧拉函数


φ(pq)= φ(p) φ(q)=(p-1)(q-1)

欧拉定理

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
aφ(n)≡1 (mod n)即1=aφ(n) mod n

模反元素

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

密匙生成过程

如何从C=ME mod N 推导 M=CD mod N

C=ME mod N => C = ME - kN
假设 M=CD mod N成立
带入可得(ME - kN)D mod N =M => MED mod N =M
由于ED ≡ 1 (mod φ(N)) 所以ED = hφ(N)+1
Mhφ(N)+1 mod N =M

后缀名

知道C N E解密

openssl rsa -pubin -text -modulus -in warmup -in 【public.pem】

可以解出 E 和 N

#python
print(0xN)

转化为十进制N
利用 yafu
factorr(N)
解出 p q

python rsatool.py -o 【private.pem】 -e 【65537】 -p 【123】-q 【123】

得到私钥private.pem

openssl rsautl -decrypt -in 【flag.enc】 -inkey 【private.pem】

私钥解密

上一篇 下一篇

猜你喜欢

热点阅读