import requests from Crypto.Util.number import * from tqdm import trange
e = 65537 n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1 ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680 h = 2**1025 - 3
primes = [int(_[0]) for _ in response.json().get("factors")]
assert prod(primes) == h + 1
cands = [] for k in tqdm(range(2**len(primes))): tmp = 1 for i inrange(len(primes)): if k % 2 == 1: tmp *= primes[i] k //= 2 tmp += 1 if is_prime(tmp): cands.append(tmp)
# check for i in tqdm(range(len(cands))): tmp_p = cands[i] assert is_prime(tmp_p) assert (h + 1) % (tmp_p - 1) == 0
L = prod(cands) d = int(pow(e, -1, L)) print(long_to_bytes(int(pow(ct, d, n))))
benaloh
public key cryptosystems, which is homomorphic.
Key Generation
Given block size r, a public/private key pair is generated
as follows:
Choose large primes p and q such that r |
(p-1), gcd(r, (p-1)/r) = 1, and gcd (r,(q - 1)) =
1;
set \[n = pq, \phi =
(p-1)(q-1)\]
\[ choose y \in Z{^*_n}\quad
such\;that\;y^{\phi/r} \not\equiv1\;mod\;n\]
Note: If r is composite, it was pointed out
by Fousse et al. in 2011that the above conditions (i.e., those stated in
the original paper) are insufficient to guarantee correct
decryption
Set \[x\;=\;y^{\phi/r}\;mod\;n\]
The public key is then \[{\displaystyle
y,n}\], and the private key is \[{\displaystyle \phi ,x}\]
Message Encryption
To encrypt message \[ m\in
Z_r\]:
Choose a random \[u \in Z{_n^*}
\];
set \[E_r(m) = y^mu^r\;mod\;n
\]
Message Decryption
To decrypt message \[ c\in
Z{_n^*}\]:
comupte \[a = c ^{\phi/r} \;mod
n\]
output \[m = log_x(a)\], i.e.,find
m such that \[x^m \;\equiv1 \; mod
n\]
Baby-step giant-step algorithm can be used to recover m in \[O(\sqrt{r})\] time and space
题里u是用lcg依次生成的,每四位对明文进行加密。我们可以知道前几组mask的值,所以相当于有4组(更多约出来也是这样的)三元方程。为了更好的求根,这里使用\[GrÖbner\]基,找到一组多项式理想的约化。求出的\[GrÖbner\]基有以下形式: \[
c^{17} + B_0 = 0\\
u + B_1*c=0\\
a + B_2=0
\] 又由lcg的推导有: \[
x_{i+1}=ax_i+c=-B_2x_i+c=...=C_{i+1}c\\
所以x{_{i}^{17}}=(C_ic)^{17}=C{_i^{17}}c^{17}=C{_i^{17}}(-B_0)\\
而C_i已知,因此可求解
\]
withopen('out.txt') as f: n, y = eval(f.readline()) R = Integers(n) z = list(map(R, f.readlines()))
y = R(y) log = {y^i: '{:x}'.format(i) for i inrange(r)}
P.<u, a, c> = PolynomialRing(R)
G = [] f = u for i, m inenumerate(b'di'.hex()): G.append(f^r - z[i]/y^int(m, 16)) f = a*f + c
B = Ideal(G).groebner_basis() print(B)
flag = '' f = -B[1].monomial_coefficient(c)*c for i inrange(len(z)): flag += log[z[i]/(f.monomial_coefficient(c)^r*(-B[0].constant_coefficient()))] f = -B[2].constant_coefficient()*f + c print(bytes.fromhex(flag))