Crypto
by Smera1d0
1.ezrsa
题干如下：
from Crypto.Util.number import getPrime
from secret import flag
p = getPrime(512)
print(p,pow(flag, 2, p))
给出了\(p\)和\({flag}^2modp\)
即我们需要解一个已知\(n\)和\(p\)，求解\(x^2=n(modp)\)中\(x\)的值
上网查阅发现\(Tonelli \ Shanks\)算法可以求解模意义下的平方根
from Crypto.Util.number import getPrime
from Crypto.Util.number import long_to_bytes
# from secret import flag
#
# p = getPrime(512)
# print(p,pow(flag, 2, p))
import gmpy2
import math
# 4124820799737107236308837008524397355107786950414769996181324333556950154206980059406402767327725312238673053581148641438494212320157665395208337575556385 13107939563507459774616204141253747489232063336204173944123263284507604328885680072478669016969428366667381358004059204207134817952620014738665450753147857
c=4124820799737107236308837008524397355107786950414769996181324333556950154206980059406402767327725312238673053581148641438494212320157665395208337575556385
p=13107939563507459774616204141253747489232063336204173944123263284507604328885680072478669016969428366667381358004059204207134817952620014738665450753147857
from Crypto.Util.number import *
def Legendre(n, p):
return pow(n, (p - 1) // 2, p)
def Tonelli_Shanks(n, p):
assert Legendre(n, p) == 1
if p % 4 == 3:
return pow(n, (p + 1) // 4, p)
q = p - 1
s = 0
while q % 2 == 0:
q = q // 2
s += 1
for z in range(2, p):
if Legendre(z, p) == p - 1:
c = pow(z, q, p)
break
r = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s
if t % p == 1:
return r
else:
i = 0
while t % p != 1:
temp = pow(t, 2 ** (i + 1), p)
i += 1
if temp % p == 1:
b = pow(c, 2 ** (m - i - 1), p)
r = r * b % p
c = b * b % p
t = t * c % p
m = i
i = 0
return r
result = Tonelli_Shanks(c, p)
print(result)
print(long_to_bytes(-result%p))
解出来方程的两根分别为result和(-result)%p
long_to_bytes(-result%p)得到flag：flag{9971e255f0c020e8e57fbae75f43d7fb}
2.hdRsa
在github上查阅到一道极为相似的题目idekctf2021/crypto/DestroyedRSA
查阅到了这道题的题解 https://angmar2722.github.io/CTFwriteups/2021/idek2021/#destroyed-rsa
此题D是从列表a里选取的，于是我们修改一下脚本
from sage.all import *
from math import gcd
import sys
from Crypto.Util.number import *
from tqdm import tqdm
sys.setrecursionlimit(100000)
def polynomial_xgcd(a, b):
"""
Computes the extended GCD of two polynomials using Euclid's algorithm.
:param a: the first polynomial
:param b: the second polynomial
:return: a tuple containing r, s, and t
"""
assert a.base_ring() == b.base_ring()
r_prev, r = a, b
s_prev, s = 1, 0
t_prev, t = 0, 1
while r:
try:
q = r_prev // r
r_prev, r = r, r_prev - q * r
s_prev, s = s, s_prev - q * s
t_prev, t = t, t_prev - q * t
except RuntimeError:
raise ArithmeticError("r is not invertible", r)
return r_prev, s_prev, t_prev
def polynomial_inverse(p, m):
"""
Computes the inverse of a polynomial modulo a polynomial using the extended GCD.
:param p: the polynomial
:param m: the polynomial modulus
:return: the inverse of p modulo m
"""
g, s, t = polynomial_xgcd(p, m)
return s * g.lc() ** -1
def factorize(N, D):
"""
Recovers the prime factors from a modulus using Cheng's elliptic curve complex multiplication method.
More information: Sedlacek V. et al., "I want to break square-free: The 4p - 1 factorization method and its RSA backdoor viability"
:param N: the modulus
:param D: the discriminant to use to generate the Hilbert polynomial
:return: a tuple containing the prime factors
"""
assert D % 8 == 3, "D should be square-free"
zmodn = Zmod(N)
pr = zmodn["x"]
H = pr(hilbert_class_polynomial(-D))
Q = pr.quotient(H)
j = Q.gen()
try:
k = j * polynomial_inverse((1728 - j).lift(), H)
except ArithmeticError as err:
# If some polynomial was not invertible during XGCD calculation, we can factor n.
p = gcd(int(err.args[1].lc()), N)
return int(p), int(N // p)
E = EllipticCurve(Q, [3 * k, 2 * k])
while True:
x = zmodn.random_element()
#print(f"Calculating division polynomial of Q{x}...")
z = E.division_polynomial(N, x=Q(x))
try:
d, _, _ = polynomial_xgcd(z.lift(), H)
except ArithmeticError as err:
# If some polynomial was not invertible during XGCD calculation, we can factor n.
p = gcd(int(err.args[1].lc()), N)
return int(p), int(N // p)
p = gcd(int(d), N)
if 1 < p < N:
return int(p), int(N // p)
n = 330961752887996173328854935965112588884403584531022561119743740650364958220684640754584393850796812833007843940336784599719224428969119533284286424077547165101460469847980799370419655082069179038497637761333327079374599506574723892143817226751806802676013225188467403274658211563655876500997296917421904614128056847977798146855336939306463059440416150493262973269431000762285579221126342017624118238829230679953011897314722801993750454924627074264353692060002758521401544361385231354313981836056855582929670811259113019012970540824951139489146393182532414878214182086999298397377845534568556100933934481180701997394558264969597606662342898026915506749002491326250792107348176681795942799954526068501499100232598658650184565873243525176833451664254917655703178472944744658628534195346977023418550761620254528178516972066618936960223660362493931786389085393392950207048675797593816271435700130995225483316625836104802608163745376633884840588575355936746173068655319645572100149515524131883813773486917122153248495022372690912572541775943614626733948206252900473118240712831444072243770979419529210034883903111038448366933374841531126421441232024514486168742686297481063089161977054825621099768659097509939405315056325336120929492838479309609958696957890570295444494277819063443427972643459784894450787015151715676537385237767990406742547664321563688829289809321534752244260529319454316532580416182438749849923354060125229328043961355894086576238519138868298499249023773237770103057707912709725417033309061308880583988666463892828633292839968866953776989722310954204550783825704710017434214644199415756584929214239679433211393230307782953067246529626136446314941258877439356094775337541321331600788042698664632064112896956898222397445497695982546922871549828242938368486774617350420790711093069910914135319635330786253331223459637232106417577225350441291
e = 65537
c = 187275367513186345104534865239994699892170904489725413330767115192172530253625393062151741036312498277557971553595091826062438445856091864605758318579599363539202154625683947568962358702545878760994434813222953503460910447662183200334960821110618746899798165363389255347363192576250804362413854445821046755759458439443253294822553986237695607000569717855942461517564526611106601774100617668231506539201297550376834067118784548951699927659889815770492684106287801610261026674778509245649501695344652216367741171392139049785280654043804502329999760613658697298671602787929199239524617160567336634126185042907593427921016129734757065504417112269027028799047579450965076835882020261162192475637278445255805339324893626400179818784574957669576516363342104273184813708475202313539634027764340858242764934872804570810575764191987921655276520658100755510986290562980055133376750812535713567917823663134974180449002466833109112866681229626239871954125027501071383217816313440079294139254989413050731511516498127225020975071747314764552267845933494600295296885808466296844091612401062566502515356974852161817112538289440970059783116540091633055220150093646069438113246518726017868258339512247175386052684861670431148484455765445960495130308147156436998327553854387741014177421559585683382003377803158283603889312107837885491964835073892174406797445622388505256985237867456926792546588756970045576002345376035346727906264683596628903417932566383221754976804148878057310066885140776352202510584461556988179369177560403923399529842871087532495739921906849249072433614545319458973155343802539527630971239359995893495205324483418191744545506744253222956232506980824457995662900264427265978239540089825733734306363153471606200228841997928021468359645661221933848545854596097640552489404777927679709089475954033350287287833943519423030861868256961619722983499902810335
a = [427,403,267,235,187,123,115,91,35,51]
for D in a:
p, q = factorize(n, D)
assert p*q == n
def roots_of_unity(e, phi, n, rounds=250):
# Divide common factors of `phi` and `e` until they're coprime.
phi_coprime = phi
while gcd(phi_coprime, e) != 1:
phi_coprime //= gcd(phi_coprime, e)
# Don't know how many roots of unity there are, so just try and collect a bunch
roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))
assert all(pow(root, e, n) == 1 for root in roots)
return roots, phi_coprime
# n is prime
# Problem: e and phi are not coprime - d does not exist
phi = (p - 1) * (q-1)
# Find e'th roots of unity modulo n
roots, phi_coprime = roots_of_unity(e, phi, n)
# Use our `phi_coprime` to get one possible plaintext
d = inverse_mod(e, phi_coprime)
pt = pow(c, d, n)
assert pow(pt, e, n) == c
# Use the roots of unity to get all other possible plaintexts
pts = [(pt * root) % n for root in roots]
pts = [long_to_bytes(pt) for pt in pts]
for pt in pts:
if b'flag' in pt:
print(pt)
用sagemath跑一下，得到：
后来欧阳学长说这个分解来自一篇论文 https://www.researchgate.net/publication/335162606_I_Want_to_Break_Square-free_The_4p_-_1_Factorization_Method_and_Its_RSA_Backdoor_Viability