HWS-easyRSA-Wp

from Kotori 学长の小测验

from secret import flag
from Crypto.Util.number import *

# seed = bytes_to_long(flag)
bits = seed.bit_length()

while True:
    p = getPrime(bits + 1) 
    if p > seed:
        break
print(p)

a = getRandomRange(1, p)
b = getRandomRange(1, p)

for _ in range(3):
    seed = (a * seed + b) % p
    print(seed)

# 31893593182018727625473530765941216190921866039118147474754069955393226712079257707838327486268599271803
# 25820280412859586557218124484272275594433027771091486422152141535682739897353623931875432576083022273940
# 24295465524789348024814588142969609603624462580932512051939198335014954252359986260009296537423802567677
# 14963686422550871447791815183480974143372785034397446416396172429864269108509521776424254168481536292904

RSA的计算过程是：

任选两个大质数p和q，p!=q，计算N=pq
计算N的欧拉函数r(n)=(p-1)(q-1)
任选一个e满足 1<e<r(n) ,且e与r(n)互质
找到d，使e*d/r(n)=x……1（x是多少不重要，重要的是余数为1）后丢弃p，
至此（n，e）为公钥，（n，d）为私钥
加密：C=Me(mod n)；解密：M=Cd（mod n）

下述推导来自 (RSA 介绍 - CTF Wiki)

消息加密 ¶

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

$$
m^{e}\equiv c\pmod N
$$

消息解密 ¶

利用密钥 d 进行解密。

$$
c^{d}\equiv m\pmod N
$$

正确性证明 ¶

即我们要证$m^{ed} \equiv m \bmod N$，已知$ed \equiv 1 \bmod \phi(N)$，那么 $ed=k\phi(N)+1$，即需要证明

$$
m^{k\phi(N)+1} \equiv m \bmod N
$$

这里我们分两种情况证明

第一种情况 $gcd(m,N)=1$，那么 $m^{\phi(N)} \equiv 1 \bmod N$，因此原式成立。

第二种情况 $gcd(m,N)\neq 1$，那么 $m$ 必然是 $p$ 或者 $q$ 的倍数，并且 $n=m$ 小于 $N$。我们假设

$$
m=xp
$$

那么 x 必然小于 q，又由于 q 是素数。那么

$$
m^{\phi(q)} \equiv 1 \bmod q
$$

进而

$$
m^{k\phi(N)}=m^{k(p-1)(q-1)}=(m^{\phi(q)})^{k(p-1)} \equiv 1 \bmod q
$$

那么

$$
m^{k\phi(N)+1}=m+uqm
$$

进而

$$
m^{k\phi(N)+1}=m+uqxp=m+uxN
$$

所以原式成立。

逆元运算 (拓展欧几里得算法)

1 2	# 模板题博客下面拿到的结论 MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算

给了n和10次lcg的output序列

用公式：a=((Xn+2-Xn+1)(Xn+1-Xn)-1)%n

题面给出了n & output

用已知信息可以求出 a
再用a，output序列，n求出b
根据output序列第一个反推出初始seed
最后使用 long_to_bytes() 函数转为字符串即可得到flag

from Crypto.Util.number import long_to_bytes

n =  31893593182018727625473530765941216190921866039118147474754069955393226712079257707838327486268599271803
output =  [
    25820280412859586557218124484272275594433027771091486422152141535682739897353623931875432576083022273940,
    24295465524789348024814588142969609603624462580932512051939198335014954252359986260009296537423802567677,
    14963686422550871447791815183480974143372785034397446416396172429864269108509521776424254168481536292904
]
# print(output[0])
MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
a = (output[2] - output[1])*MMI((output[1] - output[0]),n) % n
ani = MMI(a,n)
b = (output[1] - a * output[0]) % n
seed = (ani*(output[0]-b)) % n
plaintext = seed
print(long_to_bytes(plaintext))

lcg算法模板

消息加密 ¶

消息解密 ¶

正确性证明 ¶

逆元运算 (拓展欧几里得算法)

线性筛素数

AirDrop...