解决LCG未知参数的办法

Dawn_whisper : LCG

1、线性同余生成方法

设是一定常数，按照递推公式

其中A称为乘数(multiplier)，B称为增量(increment)，M称为模数(modulus)

LCG的生成周期理论上应该是M，但大部分情况下会小于M，如果想要追求LCG的最大周期，应符合以下几个条件：

• A与B都是正整数

• A、B、N[0]都比M要小

• B与M互质

• M的所有质因数都能整除A-1

2、攻击方法

理论上知道2个值可以知道B。3个状态值可以知道A和B。7个状态值可能知道A,B,M。

example-one:

class lcg_attack:
    # unknown B (increment)
    def lcgattack1(self, states, modulus, multiplier):
        if(len(states)<2):
            raise Exception("#####Invalid lenth of states! The lenth should be 2 at least!##### - Dawn_whisper")
        increment = (states[1] - states[0] * multiplier) % modulus
        return {'multiplier':int(multiplier), 'increment':int(increment), 'modulus':int(modulus)}

    # unknown A (multiplier)
    def lcgattack2(self, states, modulus):
        if(len(states)<3):
            raise Exception("#####Invalid lenth of states! The lenth should be 3 at least!##### - Dawn_whisper")
        multiplier = (states[2] - states[1]) * inverse(states[1] - states[0], modulus) % modulus
        return self.lcgattack1(states, modulus, multiplier)
    
    # unknown M (modulus)
    def lcgattack3(self, states):
        if(len(states)<6):
            raise Exception("#####Invalid lenth of states! The lenth should be 6 at least!##### - Dawn_whisper")
        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 self.lcgattack2(states, modulus)

'''
以下是样例执行。
'''

test = lcg_attack()

state = [150532854791355748039117763516755705063,
335246949167877025932432065299887980427,
186623163520020374273300614035532913241,
215621842477244010690624570814660992556,
220694532805562822940506614120520015819,
17868778653481346517880312348382129728,
160572327041397126918110376968541265339]

print(test.lcgattack3(state))

作者: Dawn_whisper
链接: https://dawnwhisper.github.io/2021/03/04/LCG/
来源: Dawn_whisper's blog
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

6个状态值也可能求出来，遇到求逆问题的可能需要变换crack_unknown_multiplier中state相减。

example-two:

#NewStar 2022 ezPRNG wp:
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

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

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))
    print(modulus)
    return crack_unknown_multiplier(states, modulus)

# N[i+1] = (A*N[i]+B) % M
# A,B,N均未知
hints = [32579077549265101609729134002322479188058664203229584246639330306875565342934, 30627296760863751873213598737521260410801961411772904859782399797798775242121, 59045755507520598673072877669036271379314362490837080079400207813316110037822, 29714794521560972198312794885289362350476307292503308718904661896314434077717, 3378007627369454232183998646610752441039379051735310926898417029172995488622, 35893579613746468714922176435597562302206699188445795487657524606666534642489]

sequence = hints
modulus, multiplier, increment = crack_unknown_modulus(sequence)
print('A = '+str(multiplier))
print('B = '+str(increment))
print('N = '+str(modulus))
print(crack_unknown_modulus(hints))

A = 6665518583654864024281280175260135044707462922029971254176205214742119570627
B = 70647661941803021648890247705354664245937054339520114852905142734885854842787
N = 121345174246418575181911383111384744844396268276674523949961216790284235179004

e = inverse(A, N)
print(GCD(A,N))
print(e)
flag = ((hints[0] - B) * e) % N
print(long_to_bytes(flag))