🍹LCG复习
2023-8-6
| 2023-10-27
0  |  0 分钟
type
status
date
summary
password
category
slug
icon
 
🍃
LCG基本都学了,问了 一道题,挨骂了,小师傅说很简单,我觉得很难(不敢说),最后还是自己解决咯(lcg_6),这里来复习一下(毕竟我的记性……🥀🥀🥀🥀
目录

线性同余生成器 / 线性同余方法(LCG)

📑概念

线性同余方法(LCG)是个产生伪随机数的方法
LCG的性能和随机性取决于选取的参数。如果选择恰当的参数,LCG可以生成长周期和均匀分布的伪随机数序列。然而,不恰当的参数选择可能导致序列的周期较短或者存在可预测的模式,从而影响其随机性和安全性
 
notion image
LCG的周期最大为 M,但大部分情况都会少于 M。要令LCG达到最大周期,应符合以下条件:
  • B,M 互质;
  • M 的所有质因数都能整除 A-1
  • 若 M 是4的倍数,A-1 也是
  • A,B, 都比 M 小
  • A,B 是正整数

💻代码

🔢公式及推论

公式
notion image
 
推论
(已知)

很简单,公式: b左移,两边同乘a(mod m)下的逆
 
② 求a (已知

 
③ 求b (已知

 
④ 求m (已知多组x)

🫣例题

🐾lcg_1

📑题目

🪄题解

seed 给了,a,b,n,已知所有随机数都已知,ciphertext = seed^plaintext—→plaintext = seed^ciphertext

👀wp

🐾lcg_2

📑题目

 

🪄题解

flag就是seed,已知a,b,n,c求seed,即① (已知)

👀wp

 

🐾lcg_3

📑题目

 

🪄题解

知道两个连续的随机数,已知a,n, ③ 求b (已知
b→flag

👀wp

 

🐾lcg_4

📑题目

 

🪄题解

flag→seed
知道产生的所有随机数,求seed, a,b未知,先求a ( ② 求a (已知)),再求b (③ 求b (已知 ) 然后求恢复seed (① (已知))

👀wp

🐾lcg_5

📑题目

🪄题解

和上一题一样,但是n不知道,多了一步求n (④ 求m (已知多组x))
 

👀wp

✨✨✨lcg_6

📑题目

 

🪄题解

hnp问题,构造格,恢复低位,高位已知,即可求出所有随机数
notion image

👀wp

 

二元LCG

题目

🪄题解

notion image

👀wp

 

三元LCG

LCG Revenge

 

🪄题解

 
notion image
xs = xs[1:] + [new_state]
这一步相当于一个队列,将flag的第一部分丢掉,在队尾插入新的new_state。
求seed需要在前面插入
xs = [xs0] + xs[:2]

👀wp

📎 参考文章

🥳
学会啦
 
日常训练
极客巅峰2023cryptolattice的HNP问题
目录