2024国城杯-Crypto

babyRSA

考察的是Schmidt-Samoa 密码体系

from Crypto.Util.number import *
import gmpy2
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175

pq = gmpy2.gcd(pow(2, d* n, n) - 2, n)
m=pow(c,d,pq)
print(long_to_bytes(m))
#b'D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}'

Curve

原题，通过曲线之间的映射来解题

assert (agx^2+gy2)%p==(1+dgx^2*gy2)%p

可知这是标准型的扭曲爱德华曲线

解题过程和脚本参考：Crypto趣题-曲线 | 糖醋小鸡块的blog

from Crypto.Util.number import *
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 7
e=0x10001
eG = (34120664973166619886120801966861368419497948422807175421202190709822232354059, 11301243831592615312624457443883283529467532390028216735072818875052648928463)
c=1

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)
    

    x2 = F(1+y1) / F(1-y1)
    y2 = F(x2) / F(x1)
   

    x3 = (F(3*x2) + F(A)) / F(3*B)
    y3 = F(y2) / F(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)
    

    x1 = F(x2) / F(y2)
    y1 = F(1) - (F(2) / F(x2+1))
    

    x_ = F(x1) * F(c)
    y_ = F(y1) * F(c)
    
    
    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])))
#b'D0g3xGC{SOlvE_The_Edcurv3}'

EZ_sign

b = 829396411171540475587755762866203184101195238207
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
PR.<k1>=PolynomialRing(Zmod(b))
f=(s1*k1*r2-s2*k1^2*r1)-(H1*r2-H2*r1)
res=f.roots()
print(res)
k=9455554284687443083
x=(s1*k-H1)*inverse(r1,b)%b
print(x)

b'e = 44519'

通过C = p^2 + q^2这个条件来解出p,q

一开始用res=two_squares(C)来解，发现解出来的p,q不对，又换了一种方法

from sage.all import *

N=179093209181929149953346613617854206675976823277412565868079070299728290913658

#将N转换为复数域上的整数
f = ZZ[I](N)

#获取所有因子
divisors_f = divisors(f)

#遍历所有因子，寻找满足条件的p和q
for d in divisors_f:
    a,b = d.real(), d.imag()
    if a**2 + b**2 == N:
        p = abs(int(a))
        q = abs(int(b))
        if is_prime(p) and is_prime(q):
            print(p)
            print(q)
            break
from Crypto.Util.number import *
import random
k=1865444199836044046649
print(long_to_bytes(k))
e = 44519
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
p=302951519846417861008714825074296492447
q=295488723650623654106370451762393175957
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,p*q)
print(long_to_bytes(m))