线性同余(LCG)的攻击
LCG
LCG(linear congruential generator)线形同余算法，可以用来递归生成随机数。
$ X_{n+1}=(aX_n+c) mod m $
其中a,c,m为常数，可以看到生成算法的结构十分简单，要使LCG的最大周期是m需要：
1.GCD(c,m)=1
2.m的所有质因数都能整除a-1
3.若m是4的倍数，a-1也是
4.a,c,初始X都比m小
5.a,c为正整数攻击方法
1.若a, c, m, X0 已知
若全部参数都已经知道，我们可以直接算出任意一个值
2.若c未知，但有连续两个X(X0, X1)
由定义我们有
$ X_{1}=(aX_0+c)mod m $
移一下就有
$ c=X_1-aX_0mod m $
代码
c = (x[1]-a*x[0]) % m2.若a, c未知,但有连续的三个X(X0, X1, X2)
$ X_1=(aX_0+c) mod m $
$ X_2=(aX_1+c) mod m $
$ X_2-X_1=a(X_1-X_0) mod m $
$ a=(X_2-X_1)/(X_1-X_0) mod m $
a = (x[2] - x[1]) * inverse(x[1] - x[0], m) % m有了a再求c用1中的方法就可以了
3.若a, c, m未知,但有连续的n个X(n>=4)
这个时候就不能解方程解出某些量了
我们的攻击思路是找到几个数Y满足
$ Y_i=k_im $
$ Y_i=0 mod m $
这样的几个Y的最大公因数是为m的(一定条件下)，我们要做的就是用连续的n个X找到T
所以考虑这样一个序列
$ Tn= S{n+1} - S_n $
t0 = x1 - x0
t1 = x2 - x1 = (x1*a + c) - (x0*a + c) = a*(x1 - x0) = a*t0 (aod m)
t2 = x3 - x2 = (x2*a + c) - (x1*a + c) = a*(x2 - x1) = a*t1 (aod m)就可以发现Y0 = t2*t0 - t1*t1 = (a*a*t0 * t0) - (a*t0 * a*t0) = 0 (mod m)同理我们有Y1, Y2...
然后求GCG(Y0,Y1, Y2...)即可，下面例子里面只要Y0，Y1就可以求出m。。。
from Crypto.Util.number import *
x = [2818206783446335158, 3026581076925130250, 136214319011561377,
359019108775045580, 2386075359657550866, 1705259547463444505]
# 求模数m
t = []
for i in range(5):
t.append(x[i+1]-x[i])
y = []
for i in range(3):
y.append(t[i+2] * t[i] - t[i+1] * t[i+1])
m = GCD(y[0], y[1])
# 求乘数a
a = (x[2]-x[1])*inverse(x[1]-x[0], m) % m
# 求增量c
c = (x[1]-x[0]*a) % m
# 验证
print(a, c, m, x[0])
_x = [x[0]]
for i in range(5):
_x.append((x[i] * a + c) % m)
print(_x)
希尔密码
基本原理
希尔密码是用矩阵实现的一种代换密码。
明文和密文是两个同型矩阵，解密密钥是加密密钥模26的逆元。
$ C= Menkey (mod 26) $
$ dekey= enkey^{-1} (mod 26) $
$ M= Cdekey (mod 26) $
求dekey(keyinv)解的时候代码如下
keyinv = mod(modinv(det(key), 26) * det(key) * inv(key), 26)一些问题
1.不难看出，key必须是n阶方阵，M要求是列数n的矩阵
2.key在选取时需要可逆
3.若同时知道n^2长度的明密文，就可以先求出key例子
m已知是7,4,2;19,5,4;25,19,7(HECTF...)c已知为2,3,16;18,17,15;15,22,20(没什么意义的字母串)，那么就有
>> m=[7,4,2;19,5,4;25,19,7];
>> c = [2,3,16;18,17,15;15,22,20];
>> key = mod(mod(modinv(det(m), 26)*inv(m)*det(m)*c, 26);
>> keyinv = mod(modinv(det(key) * det(key) * inv(key) ,26);
>> cc = [2,3,16;18,17,15;15,22,20;25,25,24;9,7,22;17,7,24;25,17,8;15,5,15;23,14,11];
>> mm = mod(cc*keyinv, 26); 就可以从前9位m还原出整个m
希尔密码的其他形式
对怎么将写成矩阵形式也是我们需要考虑的一部分。在上面的例子中，我们是直接把m按行的顺序写上去的，但实际上在加密时，m可以按列来写，这样我们知道的前n^2位就不能解出key。另外，我们使用的是M右乘key，其实也可以是左乘(实际上是一样的)。希尔密码利用线性变换，能够较好地抵抗频率分析，很难被频率分析攻破，安全性还是比一般的古典密码要强一些的，但线性变换本身是脆弱的。
两个简单的分解整数的方法
Pollard p-1 方法
费马小定理
若p是素数，a不是p的倍数，则有
$ a^{p-1}= 1 (mod p) $
B-Smoth数
如果一个正数的所有因子都不大于B，就称这个数是B-Smoth的
原理
若p-1是B-Smoth的数，且p-1的任意两个因子都不相等，则有
$ a^{B!}= a^{k(p-1)} = 1 (mod p) $
N=p*q,，我们要做的是找一个B，让a^{B!}-1=kp，若 1 < GCD(a^{B!-1}, N) 1，GCD算法的复杂度还是比较低的。Pollard ρ的概率性体现在随机选取c*sqrt(p)个整数(c是一个常数)，就有很大概率能找到两个数模p相等。
$ X_j = X_i (mod p) $
$ GCD( X_j-Xi,N)=p $
实际上找这两个数的时候，是使用下面的同余式来“随机”选取两个数，一般$ f(n)=n^2+a $，a为一个随机数
$ X{i+1} = f(X_i) (mod p) $
但这个递推序列在mod p的意义下一定是循环的，形似ρ。
Floyd 判环
Floyd 是一种判断序列元素是否重复的方法，当然，我们可以把所有的X存下来，但这样占内存太多了，Floyd 只需要常数个空间，具体是让j以两倍i的速度走这个环，若 $ X_j = X__i $，就可以说i已经至少走了这个环一圈。
在Floyd 判环下的pollard ρ实现
def f(x):
x = (x*x + 1) % n
return x
# x1, x2
def pollard_rho(x1, x2):
while True:
x1 = f(x1)
x2 = f(f(x2))
p = GCD(x1-x2, n)
if p == n:
return
elif p != 1:
return p, n//p
# test
n = 5929283*4338011
print(pollard_rho(2, 2))