1.univariate
题目
描述
1
| I love univariate polynomials...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
p = getPrime(512)
q = getPrime(512)
n = p*q
m = bytes_to_long(flag.encode())
e = 65537
c = pow(m,e,n)
P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]
terms = [x**i for i in range(137)]
T = RealDistribution('gaussian', 2)
coefs = [round(T.get_random_element()) for _ in range(len(terms))]
f = sum([term*coef for term,coef in zip(terms,coefs)])
w = pow(2,f(p),n)
with open('out.txt', 'w') as file:
file.write(f'{n = }\n')
file.write(f'{e = }\n')
file.write(f'{c = }\n')
file.write(f'{f = }\n')
file.write(f'{w = }\n')
n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221
|
思路：
根据题目描述univariate polynomials（单变量多项式），题目中也是反复利用p，所以可以从p开始下手。 从 w = pow(2,f(p),n)开始，这里也是我学习中感觉非常巧妙的地方，先了解前提知识费马小定理gcd(a,p)=1,$a^{p-1}\equiv 1\pmod{p}$,于是接下来就要构造出p-1。对f(p)模(p-1),就有f(p) = g(p)(p-1) + k。然后对w取p的模数。
$$
w = 2^{f(p)} = 2^{g(p)(p-1) + k} = \left(2^{g(p)(p-1)}\right) \cdot \left(2^k\right)=2^k \pmod{p}
$$
所以w除以p的模数就为2^k, 那么$w-2^{k}$就为p的倍数，然后再与n取最大公约数就可以找出p从而解决RSA问题。即gcd(w-2^k,n).
代码(错误的)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| from Crypto.Util.number import *
P.<x> = PolynomialRing(ZZ)
x = P.gens()[0]
n = 151510886600487624888537926759375027338192556324330182365859112926770109752858284462159488504727238764120612593911292154858008775463001345641311051184326218974685701057787672193003745574697137968457609530135969033403360561333863943223407215732526198691453110628598401583407984162075630768455052482583101773637
e = 65537
c = 74468088842131664480394073891613024559473817230309311952320910922177130990996003196602702376336093457990873018154873841543712071422931358036924937335888815556064840522100618318507080665149514719351519909821468981883880543654015414713368018500970500498936910817336501949914675483148862843329341461828563728789
f = -x^136 + x^135 - 2*x^134 - 4*x^132 + 2*x^130 - x^128 - 3*x^127 + 4*x^126 + 3*x^125 + 3*x^124 + x^123 + x^122 - 5*x^121 - 3*x^120 - x^119 - x^118 + x^117 + x^116 - 4*x^114 - 2*x^112 + 2*x^110 + x^109 + 2*x^108 - 2*x^107 + 3*x^106 - x^104 + 2*x^103 - x^102 + x^101 - 2*x^100 + 3*x^99 - 2*x^98 - x^97 - x^96 - 3*x^95 - x^94 - 2*x^93 - 2*x^91 + 3*x^90 - 2*x^89 - 2*x^88 + x^86 + x^85 - 2*x^84 - 3*x^83 + 2*x^82 + 3*x^79 - x^76 + 2*x^75 - x^74 + x^71 - 5*x^70 - x^67 + x^66 + x^65 + x^63 - x^61 + x^59 - 2*x^58 + 6*x^56 + x^55 + 3*x^54 - x^53 + 2*x^52 + 3*x^51 + x^50 + 2*x^49 + 3*x^47 + 2*x^46 - 4*x^45 + 3*x^44 + 3*x^43 - x^42 - 2*x^40 - 5*x^39 + x^38 + x^37 + 2*x^36 + 2*x^35 + x^34 - x^33 + x^32 - 5*x^31 + x^30 + x^29 + 2*x^28 - 2*x^27 + 3*x^26 - x^25 - x^23 - x^22 - 3*x^21 + 2*x^20 - x^19 - x^17 + 2*x^16 - 2*x^15 - 2*x^14 - 2*x^13 - 2*x^12 + 2*x^11 - 2*x^9 + 3*x^8 - 4*x^7 + 2*x^6 - 2*x^5 - 5*x^4 - 3*x^3 + 5*x^2 - 2
w = 86258923706084556733053644452456806418792871483898871193707132372143291757396867798433017660985422614532352743658877188445517898648519256573663299464811234251773841741466280567326570167017786562044635756348763128567054349991798640926148221279889174229551074668002853442182664523748992260830782387602048836221
k = f % (x-1)
k_int=ZZ(k)
q = GCD(w -2^k_int, n)
p = n // q
print(long_to_bytes(int(pow(c, inverse(e, (p-1)*(q-1)), n))))
|
代码报错了，检查大概知道了原因在于k的值最后是负数，所以直接2^k不行。
正确部分
1
2
3
4
5
| k = f % (x-1)
p = GCD(w * pow(2, -k, n) - 1, n)
q = n // p
|
解释：当k是负数时， $2^{k}\pmod{n}$实际上是$2^{-\lvert k\rvert }\pmod{n}$的模逆元。这是因为指数运算是周期性的，且模逆元可以看作是将指数“翻转”到模数的范围内。pow(2, -k, n) 计算的是 $2^{k}\pmod{n}$ 的模逆元。如果 k是负数，这意味着我们正在寻找一个数 y 使得 $2^{k}*y\equiv 1\pmod{n}$，然后乘上w再减1就是与n有共同因子。勉强理解是这样，但我数学这方面并未深入研究，所以个人感觉纠错推导过程有点牵强，日后有新理解再做修改吧。