Crypto | 密码学

openssl rsa -pubin -text -modulus -in warmup -in pub.pem

RSA

算法原理

RSA 加解密方案和签名方案都是基于以下的理论依据，即对于所有的整数 m，都满足 $$ m^{ed}\equiv\ m\left(mod\ n\right) $$

RSA 密钥对生成

输入：安全参数 l（密钥长度）
输出：RSA 公钥（n,e）和私钥 d
随机选择两个素数 p 和 q，p 和 q 的长度相同，都等于 l/2
计算 n = p * q 和欧拉函数 ø = (p-1)(q*-1)
任意选择整数 e，e 必须满足 1<e<ø,且 gcd(e,ø)=1 （gcd：最大公因数，=1即互质）
计算整数 d，d 满足 1<d<ø，且 e * d ≡ 1(mod ø) （“≡”是同余符号）

RSA 基本加密

输入：RSA 公钥（n,e）,明文 M∈[0,n-1]
输出：密文 C
计算 C = M^e mod n

RSA 基本解密

输入：RSA 公钥（n,e）,RSA 私钥 d,密文 C
输出：明文 M
计算 M = C^d mod n

RSA 签名方案

签名过程与加密过程相似，不同的是需要先将明文 M 做一次 hash 变换，压缩成特定长度的信息 h。

提供密文（xxx.enc）和公钥（pub.key/pub.pem）

使用 openssl 通过公钥获得 e （Exponent）和 n（Modulus 十六进制）

bash openssl rsa -pubin -text -modulus -in warmup -in pub.pem
分解 n 算出大素数 p 和 q

方法一：http://factordb.com/

方法二：打开 cmd，进入 yafu 所在路径，在 CMD 中运行 yafu-x64。输入`factor(30578675145816634962204467309994126955968568987449100734690153203822106214253)` （n）回车

求出私钥 d

Python 脚本（最好在 Kali 中运行）：

#coding=utf-8
#!/usr/bin/python
import math
import sys
from Crypto.PublicKey import RSA
arsa=RSA.generate(1024)
# 刚才求出来的
arsa._p=
arsa.q=
arsa.e=
arsa.n=arsa.p*arsa.q
Fn=long((arsa.p-1)*(arsa.q-1))
i=1
while(True):
    x=(Fn*i)+1
    if(x%arsa.e==0):
           arsa.d=x/arsa.e
           break
    i=i+1
private=open('private.pem','w')
private.write(arsa.exportKey())
private.close()

解密

openssl pkeyutl -decrypt -in flag.enc -inkey private.pem

模数（n，p，q）相关攻击

|p-q| 较小

基本步骤：

顺序检查 √n 的每一个整数 x，直到找到一个 x 使得 $x^2−n$ 是平方数，记为 $y^2$
那么 $x^2−n=y^2$，进而根据平方差公式即可分解 N

Coppersmith 相关攻击

广播攻击

e 相同，使用不同的 n 对同一明文 c，进行加密。

公钥指数（e）相关攻击

Rabin 算法

e = 2

私钥（d）相关攻击

维纳攻击

d（私钥）过小

离散对数问题

sage速通

$c\equiv p^x\mod{p} $

求 x

d=discrete_log(c,mod(p,q))
print (d)