signin
考点
1
2
3
4
5
6
7
8
| p1, q1 = getPrime(360), getPrime(128)
n1 = p1**4*q1
q2 = getPrime(128)
bound = p1 // (8*q1*q2) + 1
p2 = random.randrange(p1, p1 + bound)
while not isPrime(p2):
p2 = random.randrange(p1, p1 + bound)
n2 = p2**4*q2
|
考连分数，勒让德定理，其实不知道原理直接展开枚举收敛就能涉及到，参考Wiener’s Attack
所以这里
$$
\frac{n_2}{n_1}=\frac{p_1^4q_1}{(p_1+x_{102})^4q_2}\notag
$$
$x_{102}$是102位的，对于
$$
|p_1-p_2|<\frac{p_1}{8q_1q_2}\notag
$$
是完全成立的，即对$\frac{n_2}{n_1}$进行连分数展开
$$
|\frac{n_2}{n_2}-\frac{q_2}{q_1}|=\frac{q_1q_2|p_1^r-p_2^r|}{q_1^2p_1^r}\notag
$$
$\frac{q_2}{q_1}$也在这些逼近里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
from sage import *
from gmpy2 import *
from Crypto.Util.number import *
global q1, q2
pk = (1150398070565459492080597718626032792435556703413923483458704675295997646493249759818468321328556510074044954676615760446708253531839417036997811506222349194302791943489195718713797322878586379546657275419261647635859989280700191441312691274285176619391539387875252135478424580680264554294179123254566796890998243909286508189826458854346825493157697201495100628216832191035903848391447704849808577310612723700318670466035077202673373956324725108350230357879374234418393233, 1242678737076048096780023147702514112272319497423818488193557934695583793070332178723043194823444815153743889740338870676093799728875725651036060313223096288606947708155579060628807516053981975820338028456770109640111153719903207363617099371353910243497871090334898522942934052035102902892149792570965804205461900841595290667647854346905445201396273291648968142608158533514391348407631818144116768794595226974831093526512117505486679153727123796834305088741279455621586989)
c1, c2 = (361624030197288323178211941746074961985876772079713896964822566468795093475887773853629454653096485450671233584616088768705417987527877166166213574572987732852155320225332020636386698169212072312758052524652761304795529199864805108000796457423822443871436659548626629448170698048984709740274043050729249408577243328282313593461300703078854044587993248807613713896590402657788194264718603549894361488507629356532718775278399264279359256975688280723740017979438505001819438, 33322989148902718763644384246610630825314206644879155585369541624158380990667828419255828083639294898100922608833810585530801931417726134558845725168047585271855248605561256531342703212030641555260907310067120102069499927711242804407691706542428236208695153618955781372741765233319988193384708525251620506966304554054884590718068210659709406626033891748214407992041364462525367373648910810036622684929049996166651416565651803952838857960054689875755131784246099270581394)
e = 0x10001
n1, n2 = pk[0], pk[1]
for q1, q2 in sub_fraction(n1, n2):
if q1 == 0 or q2 == 0:
continue
if n1 % q1 == 0 and q1 != 1:
break
p1 = iroot(n1 // q1, 4)[0]
p2 = iroot(n2 // q2, 4)[0]
phi1 = (p1-1) * p1 ** 3 * (q1-1)
phi2 = (p2-1) * p2 ** 3 * (q2-1)
d1 = invert(e, phi1)
d2 = invert(e, phi2)
print(long_to_bytes(pow(c1, d1, n1))+long_to_bytes(pow(c2, d2, n2)))
|