2024国城杯线上Crypto-WP
Curve
task:
from secret import flag
from Crypto.Util.number import*
from gmpy2 import*
flag = b'D0g3xGC{****************}'
def gen_key(p, q):
public_key = p*p*q
e = public_key
n = p*q
phi_n = (p-1)*(q-1)
private_key = inverse(e,phi_n)
return public_key,private_key,e
p = getPrime(512)
q = getPrime(512)
N,d,e = gen_key(p,q)
c = gmpy2.powmod(bytes_to_long(flag),e,N)
print(N)
print(d)
print(c)
'''
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
'''
一条标准型的扭曲爱德华曲线
根据：https://tangcuxiaojikuai.xyz/post/187210a7.html
发现这题并没有变什么，这里就不多述了，可以直接套。
exp:
from Crypto.Util.number import *
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001
eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)
c=1
#part2 map to ECC
F = GF(p)
dd = F(d*c^4)
A = F(2) * F(a+dd) / F(a-dd)
B = F(4) / F(a-dd)
a = F(3-A^2) / F(3*B^2)
b = F(2*A^3-9*A) / F(27*B^3)
def edwards_to_ECC(x,y):
x1 = F(x) / F(c)
y1 = F(y) / F(c)
#now curve is a*x^2+y^2 = 1+dd*x^2*y^2
x2 = F(1+y1) / F(1-y1)
y2 = F(x2) / F(x1)
#now curve is By^2 = x^3 + Ax^2 + x
x3 = (F(3*x2) + F(A)) / F(3*B)
y3 = F(y2) / F(B)
#now curve is y^2 = x^3 + ax + b
return (x3,y3)
def ECC_to_edwards(x,y):
x2 = (F(x) * F(3*B) - F(A)) / F(3)
y2 = F(y) * F(B)
#now curve is By^2 = x^3 + Ax^2 + x
x1 = F(x2) / F(y2)
y1 = F(1) - (F(2) / F(x2+1))
#now curve is a*x^2+y^2 = 1+dd*x^2*y^2
x_ = F(x1) * F(c)
y_ = F(y1) * F(c)
#now curve is a*x^2+y^2 = c^2(1+d*x^2*y^2)
return (x_,y_)
E = EllipticCurve(GF(p), [a, b])
order = E.order()
eG = E(edwards_to_ECC(eG[0],eG[1]))
t = inverse(e,order)
G = t*eG
G = ECC_to_edwards(G[0],G[1])
print(long_to_bytes(int(G[0])))
#D0g3xGC{SOlvE_The_Edcurv3}
babyRSA
task:
from secret import flag
from Crypto.Util.number import*
from gmpy2 import*
flag = b'D0g3xGC{****************}'
def gen_key(p, q):
public_key = p*p*q
e = public_key
n = p*q
phi_n = (p-1)*(q-1)
private_key = inverse(e,phi_n)
return public_key,private_key,e
p = getPrime(512)
q = getPrime(512)
N,d,e = gen_key(p,q)
c = gmpy2.powmod(bytes_to_long(flag),e,N)
print(N)
print(d)
print(c)
'''
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
'''
看见p*p*q 和e=n想到了Schmidt-Samoa密码系统
Schmidt-Samoa密码系统：像rabin加密一样，其安全性基于整数因式分解的难度。但 Rabin 解密时会得到四个解，而 Schmidt-Samor 得到的是唯一解。
密钥生成
1.选取两个大的质数 p 和 q 并进行计算 N=p2q
2.计算 d=invert(N,ϕ(p∗q))
加密
对消息m，计算密文 C=mNmodN
解密
计算明文，m=Cdmod(p∗q)
关于获取pq的问题
由$N = p^2 q ，，，dN = 1 mod;(p-1)(q-1)$，通过欧拉定理可以得到：
a(p−1)(q−1)≡1modp∗q
所以：
aN∗d=a1+k∗(q−1)(p−1)≡a∗ak∗(q−1)(p−1)=a mod p∗q
所以：
k∗p∗q=aN∗ d−a
p∗q=gcd(aN∗ d−a,N)
因为 a 的取值可以是 a=2,3,4,5… , 这里方便计算我们取 2
exp:
N = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
pq = gcd(pow(2,d*N,N)-2,N)
m = pow(c,d,int(pq))
print(long_to_bytes(m))
#D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}
EZ_sign
task:
from Crypto.Util.number import *
from gmpy2 import *
from hashlib import*
import random,os
flag = b'D0g3xGA{***************}'
msg = b'e = ?'
def sign(pub, pri, k):
(p,q,g,y) = pub
x = pri
r = int(powmod(g, k, p) % q)
H = bytes_to_long(sha1(os.urandom(20)).digest())
s = int((H + r * x) * invert(k, q) % q)
return (H,r,s)
k1 = getPrime(64)
k2 = k1 ** 2
pri = bytes_to_long(msg)
a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
b = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238
pub = (a, b, g, y)
H1, r1, s1 = sign(pub, pri, k1)
H2, r2, s2 = sign(pub, pri, k2)
p = getPrime(128)
q = getPrime(128)
n = p * q
c = powmod(bytes_to_long(flag), e, n)
C = p**2 + q**2
print(f'(H1, r1, s1) = {H1}, {r1}, {s1}')
print(f'(H2, r2, s2) = {H2}, {r2}, {s2}')
print(c)
print(C)
'''
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658
'''
先看签名方式是DSA加密方法，这里的s = int((H + r * x) * invert(k, q) % q) x是e。
对应的两次签名分别是：
$$
s_1⋅k_1≡H_1+r_1⋅x(modq)\
s_2⋅k_2≡H_2+r_2⋅x(modq)\
$$
由于
$$
k_2=k_1^2
$$
我们有：
$$
s_2⋅k_1^2≡H_2+r_2⋅x(modq)
$$
消x:
第一式：
$$
x≡(s1_1*k_1-H_1)/r_1(mod q)
$$
第二式：
$$
x≡(s_2*k_1^2-H_2)/r_2(mod q)
$$
等式两边相等，消去 x：
$$
(s_1k_1-H_1)/r_1≡(s_2k_1^2-H_2)/r_2(mod q)
$$
交叉相乘得到：
$$
r_2⋅(s_1⋅k_1−H_1)≡r_1⋅(s_2⋅k_1^2−H_2)(modq)
$$
展开并整理为关于 k1 的二次方程：
$$
r_2⋅s_1⋅k_1−r_2⋅H_1≡r_1⋅s_2⋅k_1^2−r_1⋅H_2(modq)
$$
即：
$$
r_1⋅s_2⋅k_1^2−r_2⋅s_1⋅k_1−(r_1⋅H_2−r_2⋅H_1)≡0(modq)
$$
这是一个标准的二次同余方程，然后解二次同余方程求k1。
二次方程：
$$
a⋅k_1^2+b⋅k_1+c≡0(modq)
$$
系数为：
$$
a=r_1⋅s_2\
b=−r_2⋅s_1\
c=−(r_1⋅H_2−r_2⋅H_1)
$$
使用二次同余方程的求解公式：
$$
k_1=(−b±\sqrt{b^2−4ac})/(2a)(modq)
$$
1.计算判别式：
$$
Δ=b^2−4ac(modq)
$$
2.求平方根
$$
\sqrt{Δ}(modq)
$$
3.求解k1
$$
k_1≡（−b+\sqrt{Δ}）/2a(modq)
$$
或
$$
k_1≡（−b-\sqrt{Δ}）/2a(modq)
$$
一旦得到 k1，然后就可以求出x：
from sage.all import *
from Crypto.Util.number import bytes_to_long
p = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
q = 829396411171540475587755762866203184101195238207
r = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238
a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238
H1, r1, s1 = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
H2, r2, s2= 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
def solve_quadratic_congruence(a, b, c, q):
delta = (b * b - 4 * a * c) % q
if pow(delta, (q - 1) // 2, q) != 1:
raise ValueError("No square root exists for Δ mod q")
sqrt_delta = pow(delta, (q + 1) // 4, q)
k1 = ((-b + sqrt_delta) * inverse(2 * a, q)) % q
k2 = ((-b - sqrt_delta) * inverse(2 * a, q)) % q
return k1, k2
a = (r1 * s2) % q
b = (-r2 * s1) % q
c = (r2 * H1 - r1 * H2) % q
k1_solutions = solve_quadratic_congruence(a, b, c, q)
print("Possible k1 values:", k1_solutions)
k=9455554284687443083
b = 829396411171540475587755762866203184101195238207
x=(s1*k-H1)*inverse(r1,b)%b
print(long_to_bytes(x))
#e = 44519
然后求p,q的话 我先是用two_squares()函数 发现求出来的p,q虽然可以通过assert C==p**2+q**2，但是应该不是符合的p,q 。后面我就用丢番图求，大概跑了几分钟出了两个正确的p,q。最后解密即可。
exp:
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
N = 179093209181929149953346613617854206675976823277412565868079070299728290913658
e = 44519
from sympy.abc import x, y, t
from sympy.solvers.diophantine.diophantine import diop_quadratic
from Crypto.Util.number import *
import gmpy2
'''
solve = diop_quadratic(x**2 + y**2 - N, t)
print('solved')
for p, q in solve:
p, q = int(p), int(q)
if isPrime(p) and isPrime(q):
print(str(p).encode())
print(str(q).encode())
'''
p=302951519846417861008714825074296492447
q=295488723650623654106370451762393175957
assert N == pow(p, 2) + pow(q, 2)
n =p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#D0g3xGC{EZ_DSA_@nd_C0mplex_QAQ}
转载
分享
0 条评论
可输入 255 字
发布投稿
