menu gh0st
LCG攻击
138 浏览 | 2021-03-16 | 阅读时间: 约 2 分钟 | 分类: CRYPTO学习 | 标签: CRYPTO
请注意,本文编写于 264 天前,最后修改于 221 天前,其中某些信息可能已经过时。

LCG攻击

简单介绍

线性同余生成随机数的方法是LCG

递推公式:Sj+1 = (m * Sj + c) (mod n)

这里的m,c,n是设定好的常数,m是乘数,c是增量,n是模数。

LCG的周期最大为n,要达到最大需要满足:

  1. m,n互质、m,c为正整数
  2. n的所有质因数都能整除A-1
  3. m,c,s[0]小于n

代码实现:

c = ......
m = ......
n = ......
seed = ......
list = []
for i in range(...):
    c = (c+m*seed) % n
    list.append(c)
    seed = c
print(list)

攻击方式

LCG存在一些缺点,以下是一些攻击方式

1.已知m,c,n,s[0]

# 种子
s0 = 2300417199649672133
# 内部的参数
m = 672257317069504227   # the "multiplier",乘数
c = 7382843889490547368  # the "increment",增量
n = 9223372036854775783  # the "modulus",模数
#可以通过上面四个数据得到接下来的随机数
s1 = (s0*m + c) % n
s2 = (s1*m + c) % n
s3 = (s2*m + c) % n
s4 = (s3*m + c) % n

2.增量未知(c未知),已知m,n,s0,s1

m = 81853448938945944
c = # unknown
n = 9223372036854775783
# 初值和第一个计算值
s0 = 4501678582054734753
s1 = 4371244338968431602
#从推导公式可以得到
s1 = s0*m + c   (mod n)
c  = s1 - s0*m  (mod n)

攻击代码如下:

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

print crack_unknown_increment([4501678582054734753, 4371244338968431602], 9223372036854775783, 81853448938945944)

3.增量与乘数未知,已知n,s0,s1,s2

m = # unknown
c = # unknown
n = 9223372036854775783
# LCG生成的初值和后面生成的两个值
s0 = 6473702802409947663
s1 = 6562621845583276653
s2 = 4483807506768649573
#同样是计算线性方程组
s_1 = s0*m + c  (mod n)
s_2 = s1*m + c  (mod n)
s_2 - s_1 = s1*m - s0*m  (mod n)
s_2 - s_1 = m*(s1 - s0)  (mod n)
m = (s_2 - s_1)//(1 - s_0)  (mod n)

攻击代码如下:

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

print crack_unknown_multiplier([6473702802409947663, 6562621845583276653, 4483807506768649573], 9223372036854775783)

4.增量,乘数和模数都未知,已知s0,s1,s2,s3......

m = # unknown
c = # unknown
n = # unknown
s0 = 2818206783446335158
s1 = 3026581076925130250
s2 = 136214319011561377
s3 = 359019108775045580
s4 = 2386075359657550866
s5 = 1705259547463444505
s6 = 2102452637059633432
#这次用线性方程式不好解决的了,因为对于每一个方程,我们是不知道前一个模数,因此我们将形成的每个方程都会引入新的未知量:
s1 = s0*m + c  (mod n)
s2 = s1*m + c  (mod n)
s3 = s2*m + c  (mod n)
s1 - (s0*m + c) = k_1 * n
s2 - (s1*m + c) = k_2 * n
s3 - (s2*m + c) = k_3 * n

这就相当于六个未知数和三个方程。所以线性方程组是不可能行得通的了,但是数论里面有一条很有用:如果有几个随机数分别乘以n,那么这几个数的欧几里德算法(gcd)就很可能等于n。

n = 123456789
reduce(gcd, [randint(1, 1000000)*n, randint(1, 1000000)*n, randint(1, 1000000)*n])
#out:123456789
X = 0 (mod n)
X != 0
#我们选取满足上面两个式子的X,只要取多个这样子的X,就可以解出n的值,我们引入T(n) = S(n+1) - S(n)
t0 = s1 - s0
t1 = s2 - s1 = (s1*m + c) - (s0*m + c) = m*(s1 - s0) = m*t0 (mod n)
t2 = s3 - s2 = (s2*m + c) - (s1*m + c) = m*(s2 - s1) = m*t1 (mod n)
t3 = s4 - s3 = (s3*m + c) - (s2*m + c) = m*(s3 - s2) = m*t2 (mod n)
#计算
t2*t0 - t1*t1 = (m*m*t0 * t0) - (m*t0 * m*t0) = 0 (mod n)
#多次计算就可以得到多个X,进而利用数论的性质求解n

攻击代码如下:

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

print crack_unknown_modulus([2818206783446335158, 3026581076925130250,
    136214319011561377, 359019108775045580, 2386075359657550866, 1705259547463444505])
#或者笨办法求出x1,x2......
x1 = t2*t0 - t1*t1
x2 = t3*t1 - t2*t2
x3 = t4*t2 - t3*t3
x4 = t5*t3 - t4*t4
x5 = t6*t4 - t5*t5
x6 = t7*t5 - t6*t6
x = [x1,x2,x3,x4,x5,x6]
n = abs(reduce(libnum.gcd, x))

附上基本是粘贴的博客

https://zeroyu.xyz/2018/11/02/Cracking-LCG/

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!