做题记录

做题

cycling

Carmichael function

$$定义为a^{m} \equiv 1 \;mod\;n成立的最小正整数m ，其中( a , n ) = 1 ，将m记作\lambda(n)\\ 换言之，如果a^{m} \equiv 1 \;mod\;n，则m\;|\;\lambda(n)$$

Carmichael定理

$$\lambda(p^r)=\left\{ \begin{aligned} & \varphi(p^r) \;if\;p^r = \;2,3^r,4,5^r,7^r等奇数素数以及2、4 \\ & \frac{1}{2}\varphi(p^r) \;if\;p^r = \;8,16,32,64等2的3次幂以上\\ \end{aligned} \right.$$

计算$\lambda(n)$

由整数分解定理

$$n = p{_{1}^{r_1}}p{_{2}^{r_2}}···p{_{n}^{r_n}}$$

那么

$$\lambda(n) = lcm(\lambda(p{_{1}^{r_1}}),\lambda(p{_{2}^{r_2}}),···,\lambda(p{_{n}^{r_n}}))$$

h+1易分解为17个小素数，且没有2次及以上的素数

$$\because h+1\; |\;\lambda(\lambda(n))\\ \therefore 用primes相乘+1判断是否为素数，并凑出可能的\lambda(n)\\$$

import requests
from Crypto.Util.number import *
from tqdm import trange

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
h = 2**1025 - 3


response = requests.get(r'http://factordb.com/api', params={"query": str(h + 1)})

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 in range(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:

1. Choose large primes p and q such that r | (p-1), gcd(r, (p-1)/r) = 1, and gcd (r,(q - 1)) = 1;

2. set $n = pq, \phi = (p-1)(q-1)$

3. $$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

4. 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$:

1. Choose a random $u \in Z{_n^*}$;
2. set $E_r(m) = y^mu^r\;mod\;n$

Message Decryption

To decrypt message $c\in Z{_n^*}$:

1. comupte $a = c ^{\phi/r} \;mod n$
2. 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已知，因此可求解$$

r = 17

with open('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 in range(r)}

P.<u, a, c> = PolynomialRing(R)

G = []
f = u
for i, m in enumerate(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 in range(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))