ailixiyaji/re0-rsa-

好难啊qwq

re0-rsa-'s Issues

Re0

Re0：从零开始的密码学习生活

但是一点不会是不是搞错了什么

公钥（public key)私钥（private key）

public modulus（模数） 随机选择两个不同大质数 p 和 q，计算 N=p×q

φ(N)=φ(p)φ(q)=(p-1)(q−1)

e

k

padding

mod()

建立矩阵（matrix）

选择一个小于 φ(N) 的整数 e，使 e 和 φ(N)互质。并求得 e 关于 φ(N) 的模反元素，命名为 d，有 ed≡1(modφ(N))
在数论中，如果两个或两个以上的整数的最大公约数是 1 ，则称它们为互质。

此时，(N,e) 是公钥，(N,d) 是私钥。

为了加快解密速度，实现时通常不直接计算 ，而是使用**余数定理（CRT）

RSA-CRT 将指数 分成两部分 dp = d mod (p − 1)和dq = d mod (q − 1)。
借助预先计算出的值d qinv = q^−1 mod p，通过计算就可以恢复信息。
利用加纳公式（ Garner’s formula）m = mpqqp + mq(1 − qqp) = (mp − mq)qqinv + mq mod N

Encryption（加密） 将消息 以一个双方约定好的格式转化为一个小于 N，且与 N 互质的整数 m。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：m^e≡c(modN)

Signatures（解密） cd≡m(modN)

我们知道 d < (p − 1)(q − 1)，所以 k < e。攻击者不知道 k的值，但由于在实践中一般是e ≤ 65537，因此对 k的所有可能值进行暴力破解是有效的。

假设模数（mod）为 N ，N 具有一个因子 b≥Nβ,0<β≤1。
多项式(polynomial) F 的次数为 δ。
该方法可以找到该多项式所有的整数根（integral root）x0，要求 |x0|<cN^（β^2/δ） 。
目标是找到在modN 意义下多项式所有的根,LLL（没看懂）方法找到
1.与该多项式具有相同根 x0
2.更小系数
3.定义域为整数域的多项式g，两个多项式在mod意义下的整数跟相同。

1.Lattice attacks on low-exponent RSA with bad padding（对有不良填充的低分量RSA格攻击）

使用连续比特恢复 RSA 密钥的主要算法技术是将问题表述为寻找一个整数多项式的小根，然后使用格基还原法（lattice basis reduction）解决这个问题。

攻击者知道公共模N 、密文C 以及在加密前预先添加到未知信息m 中的填充 。攻击a者希望恢复 m。
对于未知的m ，我们有 c =(a+ m)3 mod N。让f(x) = (a+x)3 −c ；我们设置的问题是希望找到一个满足f(m) ≡ 0 mod N的多项式的小根 。

构建网格设 f的系数为f(x) = x^3 +f2x^2 +f1x+f0 。设 M = 2^16为根m 大小的上限。我们构建矩阵

然后，我们对矩阵应用 LLL 格基还原算法从网格中提取多项式并找出它的根。然后，我们构建多项式v =(−0x66543dd72697M3, −0x35c39ac91a11c04M2, 0x3f86f973d67d25eae138M,− 0x10609161b131f d102bc2a8)多项式 有一个整数根，即0x42 ，它是 m的理想解。

这种特定的44 网格结构可以找到最大大小为N^（1/16） 的根。对于我们在示例中使用的小密钥大小，这只是16 比特，但由于它直接随模的大小扩展，因此对于 1024 位 RSA 模，同样的网格结构足以学习 170 未知比特的信息，或者对于 2048 位 RSA 模，足以学习 341 比特的信息。在44 网格基础上的网格缩减是瞬时的。

这个矩阵的行对应于多项式f(x) 和Nx^2、Nx的系数向量。我们知道这些多项式中的每一个在 x=m处求值都将是 0 moduloN 。每一列都按 M的幂进行缩放，因此该网格中任何向量的l1 准则都是在r 处求值的相应（未缩放）多项式值的上界。对于网格中的一个向量r v = (v3M3, v2M2, v1M, v0)
|f(m)| = |v3m3 + v2m2 + v1m + v0| ≤ |v3M3| + |v2M2| + |v1M| + |v0| = |v|1for any |m| ≤ M

2.Factorization from consecutive bits of p（p 的连续比特）

给定 N=pq的连续已知最有效位的因式分解p 。
让 成为一个 RSA 模，其中 p和 q大小相等。选择一个数字小到足以fit on the page，我们就有了一个 240 位的 RSA 模.我们假设N 已知。假设我们知道p 的最重要bit ** b** 的大部分连续位，因此p=a+r，其中我们不知道 r，但知道 a = (2^l)b 的值。这里 l=30是未知位的bits，或者说是已知位的左移。
a = 0x68323401cb3a10959e7bfdc0000000
有某个值 f(x) = a+x，使得f(r) = p ≡ 0 。
未知的r 是很小的，特别是对于已知的某个边界R ，|r|<R 。这里，R=2^30 。

在网格基 上运行 LLL 算法。让v = (v2R2, v1R, v0) 成为还原基中最短的向量。

v =(−0x0x17213d8bc94R2, −0x1d861360160a4f86181R,0xf9decdc1447c3f3843819a5d)

我们构成一个多项式f(x) =−0x17213d8bc94x^2 − 0x1d861360160a4f86181x+ 0xf9decdc1447c3f3843819a5d 。

可以重建 a + r并验证gcd(a + r, N) 因数N 。
这种3*3 网格结构适用于任何|r| < p^1/3 ，并随着p的增加而直接扩展。在我们的示例中，我们选择了p和q ，因此它们有 120 位，而 r有 30 位。然而，同样的结构可以从 1024 位 RSA 模的 512 位因子中恢复170 位，或从 2048 位 RSA 模的 1024 位因子中恢复 341 位。

3.RSA key recovery from least significant bits of p(从最小有效位恢复 RSA 密钥p)

如果该未知位从l 位开始，则输入多项式的形式为f(x) = (2^l)x + a 。这个多项式可以乘以2^(-l)mod N

4.RSA key recovery from middle bits of p( 从密码表的中间位恢复 RSA 秘钥p)

5.RSA key recovery from multiple chunks of bits of p(多比特块恢复秘钥)

6.RSA key recovery from many nonconsecutive bits of p(从许多非连续比特位恢复秘钥)

同4

7.Partial recovery of RSA dp（部分恢复）

8.Partial recovery of RSA d from most significant bits is not possible（无法从最重要部分恢复）

9.Partial recovery of RSA d from least significant bits（从最小有效位恢复）

10.Random known bits of p and q（随机已知位）

11.Random known bits of the Chinese remainder coefficients d mod(p − 1) and d mod (q − 1)（中文余数系数的随机已知位 ）

12.Recovering RSA keys from indirect information（间接信息）

13.Random known bits without redundancy（无冗余的随机已知比特）