羊城杯2021 Crypto wp

1.bigrsa

题目

from Crypto.Util.number import *
from flag import *n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n1)
c = pow(c, e, n2)print("c = %d" % c)# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

解题

大致意思是题目给出两个模数，对一个明文进行两次加密。

我们可以利用这两个模数来求出他们的公约数，这样就可以分解模数。
之后只要对密文进行两次解密就行了！

代码：

from Crypto.Util.number import *
import gmpy2n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p1 = p2 = gmpy2.gcd(n1,n2)q1 = n1 // p1
q2 = n2 // p2
d1 = gmpy2.invert(e,(p1-1)*(q1-1))
d2 = gmpy2.invert(e,(p2-1)*(q2-1))m1 = pow(c,d2,n2)
m2 = long_to_bytes(pow(m1,d1,n1))print(m2)
#b'SangFor{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}'

2. RSA?

题目

import os
from Crypto.Util.number import *
'''
flag = "GWHT{xxxxxxxxx}"
p = getPrime(256)
q = getPrime(256)
n = p*q
N = (p-1)*(q-1)
e = 65537
Mx = bytes_to_long(os.urandom(30))
My = bytes_to_long(flag)
Z1 = (Mx*My)%n
inv_Z1 = inverse_mod(Z1, n)
inv_2 = inverse_mod(2, n)
X = ((Z1+inv_Z1)*inv_2)%n
Y = My
inv_Y = inverse_mod(Y, n)
a = ((inv_Z1-X)*inv_Y)%n
D = (a*a)%nxy = lambda (x1,y1),(x2,y2) : ((x1*x2+D*y1*y2)%n, (x1*y2+x2*y1)%n)
def getloop((x,y), e):ret = (x, y)for i in range(e-1):ret = xy(ret, (x,y))return retprint n 
print getloop((X, Y), e)
print a

解题

Mx = bytes_to_long(os.urandom(30))
My = bytes_to_long(flag)
Z1 = (Mx*My)%n
inv_Z1 = inverse_mod(Z1, n)
inv_2 = inverse_mod(2, n)
X = ((Z1+inv_Z1)*inv_2)%n
Y = My
inv_Y = inverse_mod(Y, n)
a = ((inv_Z1-X)*inv_Y)%n
D = (a*a)%n

通过这段代码，可以发现除$Mx$ ,$My$ ，$n$ 以外的其它数，基本元素均是由$Mx$ ,$My$组成，而我们要求的也是$My$，所以可以将 $Z_1$，$inv\_Z_1$ ， $X$ ， $Y$ ，$inv\_Y$ ，$a$ ，$D$都化成只含$Mx$ ,$My$ 。
故
$Z_1=Mx?My\%n$
$inv\_Z_1=\frac{1}{Mx?My}\%n$
$X=\frac{1+M{y}^2?M{x}^2}{2?Mx?My}\%n$
$Y=My$
$inv\_Y=\frac{1}{My}\%n$
$a=\frac{1?M{y}^2?M{x}^2}{2?Mx?M{y}^2}\%n$
$D=(\frac{1?M{y}^2?M{x}^2}{2?Mx?M{y}^2}{)}^2\%n$

同样在getloop中的循环找 x_i , y_i 规律,写出前几项就可以发现规律：

第一次循环，n = 1,$x1=\frac{1+M{x}^4?M{y}^4}{2?M{y}^2?M{x}^2}$ , $y1=\frac{1+M{x}^2?M{y}^2}{Mx}$
第二次循环, n = 2,$x2=\frac{1+M{x}^6?M{y}^6}{2?M{y}^3?M{x}^3}$ , $y2=\frac{1+M{x}^2?M{y}^2+M{x}^4?M{y}^4}{M{x}^2?My}$
第三次循环, n = 3,$x3=\frac{1+M{x}^8?M{y}^8}{2?M{y}^4?M{x}^4}$ , $y3=\frac{1+M{x}^2?M{y}^2+M{x}^4?M{y}^4+M{x}^6?M{y}^6}{M{x}^3?M{y}^2}$
所以规律为$x_n=\frac{1+M{x}^{2?n+2}?M{y}^{2?n+2}}{2?M{y}^4?M{x}^4}$ , $y3=\frac{1+M{x}^2?M{y}^2+M{x}^4?M{y}^4+...+M{x}^{2?n}?M{y}^{2?n}}{M{x}^n?M{y}^{n?1}}$

$n\in [1,e?1]$

这样的话，代码的内容基本上都转化为了公式，而现在就要利用公式来求$My$

$a?y_n=\frac{(1?M{x}^2?M{y}^2)?(1+M{x}^2?M{y}^2+M{x}^4?M{y}^4+...+M{x}^{2?n}?M{y}^{2?n})}{2M^{n+1}?M{y}^{n+1}}(modn)$
$=\frac{1?M{x}^{2?n+2}?M{y}^{2?n+2}}{2M^{n+1}?M{y}^{n+1}}(modn)$
$=x_n?(Mx?My{)}^{n+1}(modn)$
于是，我们可以利用给出的$a$，$y$，$x$ 来求解$(Mx?My{)}^{n+1}$
因为$n\in [1,e?1]$，所以当循环完成后n + 1 = e = 65537。

令C = $(Mx?My{)}^{n+1}$ , M = $Mx?My$,即有$C=M^e(modn)$
，就很容易解出M = $Mx?My$的值
但是我们求的是$My$，需要从$Mx?My$中提取$My$。
而$a=\frac{1?M{y}^2?M{x}^2}{2?Mx?M{y}^2}\%n$中的分母正好多出了一个$My$，从而推出$My=\frac{1?(Mx?My{)}^2}{2(Mx?My)?a}$
这才得到了$My$的值，从而也就知道了flag。

from Crypto.Util.number import *
import gmpy2
n = 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023
(x,y) = (5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785)
a = 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141
p = 115718235064789220654263009993128325569382592506655305434488398268608329541037
q = 115718235064789220654263009993128324769382192706654302434478391267607309966379
e = 65537
D = (a*a)%n
Mx_My_65537 = (x - a*y)%n
d = gmpy2.invert(e,(p-1)*(q-1))
Mx_My = pow(Mx_My_65537,d,n)
My = ((1 - Mx_My**2)*(gmpy2.invert(2,n) * gmpy2.invert(Mx_My,n) * gmpy2.invert(a,n)))%n
print(long_to_bytes(My))
#flag = b'GWHT{pell_equation_is_very_interesting}'

参考：
2021羊城杯 部分CRYPTO WP

3.Easy_Rsa

题目

from Crypto.Util.number import *
from flag import flag
import gmpy2def gen_prime(nbits, gamma):g = getPrime(int(nbits * gamma))alpha = 0.5 - gammawhile True:a = getRandomNBitInteger(int(alpha * nbits))p = 2 * g * a + 1if isPrime(p):b = getRandomNBitInteger(int(alpha * nbits))q = 2 * g * b + 1h = 2 * g * a * b + a + bwhile not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:b = getRandomNBitInteger(int(alpha * nbits))q = 2 * g * b + 1return p, qdef encrypt(nbits, gamma):p, q = gen_prime(nbits, gamma)n = p * qe = getPrime(16)while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:e = getPrime(16)m = bytes_to_long(flag)c = pow(m, e, n)return n, e, cn, e, c = encrypt(1024, 0.48)
print 'n =', n
print 'e =', e
print 'c =', c# n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
# e = 58337
# c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

解题

可以看出 $p?1$ , $q?1$ 具有一个很大的相同的因数，可以利用Rho算法来快速分解大数。
Rho算法
文献.pdf

import gmpy2,sympy
from Crypto.Util.number import *def f(x, n):return (pow(x, n - 1, n) + 3) % ndef rho(n):i = 1while True:a = getRandomRange(2, n)b = f(a, n)j = 1while True:p = GCD(abs(a - b), n)print('{} in {} circle'.format(j, i))if p == n:breakelif p > 1:return (p, n // p)else:a = f(a, n)b = f(f(b, n), n)j += 1i += 1n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
e = 58337
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668p,q = rho(n)
d = gmpy2.invert(e,(p-1)*(q-1))m = pow(c,d,n)
print(long_to_bytes(m))
#b'SangFor{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}'