四道题目，三道RSA。最后一道更像是算法题目，不懂算法。

我发现，这三道题目都在RSA的底层数学逻辑上做了很深的功夫，可以看出出题人相当有水平。第三题研究了很长时间，整整一个下午加晚上都在和这道题死磕，最后还是耻辱放弃，以后我肯定能做出来。

背负着智慧三角的力量，胜利是必然的！！！

insecure_padding

Task

from Crypto.Util.number import *
from secret import flag

assert flag[:7]==b'DASCTF{' and flag[-1:]==b'}'
flag = flag[7:-1]
assert len(flag) == 20

def my_rsa_padding(m):
    e = 3
    p = getPrime(1024)
    q = getPrime(512)
    n = p*q
    pad = long_to_bytes(777*p+666)
    m = bytes_to_long(m+pad)
    assert m < n
    c = pow(m, e, n)
    return c, e, n, len(pad)

print(my_rsa_padding(flag))
"""
(1193333119181381225632504634109476125461718042032463066180160159530821008151288619914035008577444580123023483451618973104785206841878926362053767758825420307104536873166791566346076985369125399199847240472385775854381103486198612767122009780041785220241663307760491699892303259600093817957324293717178123893664313547870460181936283477289029428950611459484805364390503487619676794166358047636359524103138509752217552291498141048509236471615548177017684230320627457, 3, 1345974903151028106176188777499919289689885052993818155551239513162986365479059645712347472719763678799888312063629534224676532524320490059299999431455806985776161385636341889882617880557005343019148419971407438285456200388681742721058826527478752200546957229924712840178042652788689761602760552457535667154424045780264689394678280189407534443469304768432295723527834457536647823320807747766083091825227699222804959851169910812454526260545186908048603618547346519, 130)
"""

Think

关于填充问题，我们首先要了解填充之后的flag是什么样子的。所以首先讲一下关于这个的规则，重点是这两行代码。

pad = long_to_bytes(777*p+666)
m = bytes_to_long(m+pad)

填充的数字是将777*p+666转化为字符串，然后拼接到m后面，再将拼接后的字符串转换成长整数。

a = 'a'
b = 'b'
print(a+b)
#ab

然后我们再具体讲一下bytes_to_long是如何工作的。

bytes_to_long 是一个把字节序列转换为一个长整数的函数。它会把整个字节序列视为一个大端的整数进行解释。比如单独对a进行bytes_to_long是97，单独对b进行bytes_to_long是98。但是"ab"就是24930。具象来看就是将"a"和"b"的二进制/十六进制前后拼接，然后再转换成十进制进行数学运算。

或者换一种方式解释。ab在输入的时候，a比b高一个字节位，而一个字节位有8个比特位。2^8=256。97(a)*256 + 98(b)=24930.

那么'abc'转换成长整数是什么样的呢？

按照上面的思路，是97*2^16 + 98*2^8 + 99，答案是6382179。

那么换个思路呢？直接将24980*2^8+99，答案也是6382179。

a在'ab'中比b高一位，ab在'abc'中比abc高一位，a在'abc'中比bc高两位。所以我们就可以得到这样一个规律，一个字符串每往前进一位，它的长整数就乘以2^8，进两位就乘以2^16。就是这样。

那么回到我们的题目，m = bytes_to_long(m+pad)。

我们的m可以看作bytes_to_long(m*2^8n) + bytes_to_long(pad)。n等于pad的位数 。

pad的位数在题目最后给我们了，是130。130*8=1040。

所以我们的m就可以构造为bytes_to_long(m*2^1040 + pad）

那么可得C≡(m×2^1040+777p+666)^3 mod n。

接下来是一个非常简单的化简，C≡(m×2^1040+666)^3 mod p。

接下来，你们有没有听说过coppersmith找小根？

我们可以用coppersmith找出我们的小根m。

copper，永远的神！

Exp

from sage.all import *
from Crypto.Util.number import *

c = 1193333119181381225632504634109476125461718042032463066180160159530821008151288619914035008577444580123023483451618973104785206841878926362053767758825420307104536873166791566346076985369125399199847240472385775854381103486198612767122009780041785220241663307760491699892303259600093817957324293717178123893664313547870460181936283477289029428950611459484805364390503487619676794166358047636359524103138509752217552291498141048509236471615548177017684230320627457
e = 3
n =  1345974903151028106176188777499919289689885052993818155551239513162986365479059645712347472719763678799888312063629534224676532524320490059299999431455806985776161385636341889882617880557005343019148419971407438285456200388681742721058826527478752200546957229924712840178042652788689761602760552457535667154424045780264689394678280189407534443469304768432295723527834457536647823320807747766083091825227699222804959851169910812454526260545186908048603618547346519
lenpad = 130
R.<x> = PolynomialRing(Zmod(n))
f = (x * 2**1024 + 666)**3 - c
f = f.monic()
m = f.small_roots(X=2**250,beta=0.5,epsilon=0.03)[0]
print(long_to_bytes(int(m)))
#然后包进DASctf{}里就可以了

结果........list index of range!!!!!!

我不服气，assert len(flag) == 20，就算flag全是z也不过699228234330863356944508037613280503521661844090。我2的250次方兜不住它？为什么跑不出来呢。思路和代码都没错误啊。

这样的问题其实也不是没遇到过，第一次用sagemath的时候复制的别人的copper脚本，设置好的参数和范围，我这边也跑不出来，最后重新改的参数和范围才跑出来的。我的电脑是不是有问题啊。

EZ_RSA_5

此trick在hitcon2019中亦有记载，甚至难度还高了一点？

感叹外国的CTF还是比国内领先啊，hitcon五年前的题了都，五年前我还初三呢

https://github.com/pcw109550/write-up/tree/master/2019/HITCON/Lost_Modulus_Again

Task

from Crypto.Util.number import *
import gmpy2
from secret import flag

m=bytes_to_long(flag)

p=getPrime(512)
q=getPrime(512)
e=65537
n=p*q

phi =(p-1)*(q-1)
p1 = gmpy2.invert(p,q)
q1 = gmpy2.invert(q,p)

c = pow(m,e,n)
P = pow(m,p,n)
Q = pow(m,q,n)
K = P*Q

phi_K=(P-1)*(Q-1)
d=inverse(e,phi_K)
dp=d%(P-1)

print("p1 =",p1)
print("q1 =",q1)
print("phi =",phi)
print('K = ',K)
print('dp = ',dp)

'''

p1 = 2636020992576559969055483957060200941734026828135579110378070592732862908176025649071069827089999996350015210043636523971348821850565913816154887832272305
q1 = 7886513101716991094728039196608717849158915101115291363845210343608904418304571443491051842715241903123031976527174063528298034452215971449949398656913945
phi = 115505961171763309547793530782914001823768056515083869218337105172209622283311582473506324170565971054492347897941697574972266679462737991988159654350224823122310342866537098903019067348499259894857405865405379172014292034138593409888061494667098647947191077373457924105640280156013690526621147715122416478264
K =  3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704697742640442010893811830528349203606514981272974154582682489532205008927740716725904614810707240205595586894383039181983075907373556864396176123489201513001026708388504250801785422323131912494763394371589512367935031912074535458595633402462463667072692589863355712935552396330534658448628449816139943205511637
dp =  53589538487289875479012684116246778147274714450209576105277816626983528993595125486641833027290704077932308918237978477501981907543847383655230156916578979044682282870153618849419762148348930652564442177633668690473147864322377146889467662769284463217004314651469157455678363085510100707437896627192687923547

Think

这一题也是普通的ezRSA，然后p1是p的逆元模q，q1是q的逆元模p。C，P，Q是（），总之有那么几个参数。

我之前写过这样一个程序，已知N，dp或者dq，e就能将n分解。但那是针对n的两个因数是素数的情况下。这里的K并不能保证P和Q都是质数。所以我们要尽可能多的遍历可能值。把所有的可能值都列出来，人眼筛选一下可能的P和Q。但是能跑出来的p和q太多了，正如我们上面所说的不能保证P和Q都是质数。先把代码贴一下吧。数学原理以后再水一篇文章。

import gmpy2

def recover_all_ps(dp, e, n):
    factors = set()
    for a in range(2, 20000):
        left = pow(a, e * dp, n) - a
        p = gmpy2.gcd(left, n)
        if p != 1 and p != n:
            factors.add(p)
    return factors

dp = 53589538487289875479012684116246778147274714450209576105277816626983528993595125486641833027290704077932308918237978477501981907543847383655230156916578979044682282870153618849419762148348930652564442177633668690473147864322377146889467662769284463217004314651469157455678363085510100707437896627192687923547
e = 65537
n = 3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704697742640442010893811830528349203606514981272974154582682489532205008927740716725904614810707240205595586894383039181983075907373556864396176123489201513001026708388504250801785422323131912494763394371589512367935031912074535458595633402462463667072692589863355712935552396330534658448628449816139943205511637

factors = recover_all_ps(dp, e, n)
for p in factors:
    q = n // p
    print("p =", p)
    print("q =", q)

我在a属于(0,2000]中爆破出了以下可能性

暂时无法在飞书文档外展示此内容

可以看到还是很多的，再往大的爆我相信还会更多

当然还有另一个办法，这个也是要牵扯RSA的加密逻辑。

我们知道，在RSA中满足d*e ≡ 1 mod  ϕ(n)（在这题中是ϕ(K)

虽然这个也不是rsa，不过区别只在P和Q是不是素数，不影响的

K = P*Q phi_K=(P-1)*(Q-1) d=inverse(e,phi_K) dp=d%(P-1)

也就是说，e * d - 1 = k * ϕ(K)（k是某个整数

同时因为（P-1）是ϕ(K)的因数，所以e * d - 1 = k * (P-1)

同时，我们也有dp=d%(P-1)，那么可以得出d = k1 * (P−1) + dp

那么我们就可以写出同余式dp*e ≡ 1 + k⋅(p−1)

转化一下就是 dp*e - 1 ≡k*(P−1)

这里面有四个未知量，有一个k本来就是要爆破的，这还解不出来P？

-------------Q.E.D

根据数学推导写脚本

from Crypto.Util.number import *
import gmpy2

dp = 53589538487289875479012684116246778147274714450209576105277816626983528993595125486641833027290704077932308918237978477501981907543847383655230156916578979044682282870153618849419762148348930652564442177633668690473147864322377146889467662769284463217004314651469157455678363085510100707437896627192687923547 
e = 65537
K = 3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704697742640442010893811830528349203606514981272974154582682489532205008927740716725904614810707240205595586894383039181983075907373556864396176123489201513001026708388504250801785422323131912494763394371589512367935031912074535458595633402462463667072692589863355712935552396330534658448628449816139943205511637

for i in range(1, e):
    if (dp * e - 1) % i == 0:
        P = (dp * e - 1) // i + 1      
        if K % P == 0:
            Q = K // P

            print("P=",P)
            print("Q=",Q)
            

#P=89706459192396530593549443920371512846107199328839237547229758327568121878195799315931797683572600269608687634404290962684155916188631860811034680949192525086238991914925741833782609688548028611711472171734508568556069872649373734405124829887118997365400928949792704456407061927794321219467125520582544212039
#Q=44544241394539455087080003827042433390596610554187086515097380871947145536991877216409262767617552724165444473076549560658417398194657348107209262950353565993877966067642602951964287850776064487853037993132356275513691026700801254797314898063932907251598380047383415220014112316421578570998223070668797351683

那么有了P和Q，我们还得想办法解出来p和q。

phi =(p-1)*(q-1) p1 = gmpy2.invert(p,q) q1 = gmpy2.invert(q,p) c = pow(m,e,n) P = pow(m,p,n) Q = pow(m,q,n)

我们有phi，有p1，p2，也解出来了P和Q。

import sympy
import gmpy2
x = 2636020992576559969055483957060200941734026828135579110378070592732862908176025649071069827089999996350015210043636523971348821850565913816154887832272305
y = 7886513101716991094728039196608717849158915101115291363845210343608904418304571443491051842715241903123031976527174063528298034452215971449949398656913945
phi = 115505961171763309547793530782914001823768056515083869218337105172209622283311582473506324170565971054492347897941697574972266679462737991988159654350224823122310342866537098903019067348499259894857405865405379172014292034138593409888061494667098647947191077373457924105640280156013690526621147715122416478264

def solve(a, b, c):
    D = b ** 2 - 4 * a * c
    # assert gmpy2.is_square(D)
    x1 = (-b + gmpy2.isqrt(D)) // (2 * a)
    x2 = (-b - gmpy2.isqrt(D)) // (2 * a)
    return x1, x2

a = x - 1
b = x * y - 1 + (x - 1) * (y - 1) - phi
c = (y - 1) * (x * y - 1)
k1, k2 = solve(a, b, c)
if (x * y - 1) % k1 == 0:
    k2 = (x * y - 1) // k1
elif (x * y - 1) % k2 == 0:
    k1, k2 = k2, (x * y - 1) // k2
else:
    assert False

p, q = x + k2, y + k1
print(p)
print(q)

#11198469463791545278619772990550048972153411253872703306559384762341904625491585546901465814421769882976230432056883880344770707467660327961608441011384163
#10314441767710606102937195215834089659678641178199945218290612694615948834633793866983953938981209335187624023708779675532856424652499590260914133511985373

然后有了p和q，正当我想去写解题脚本的时候忽然感觉十分有九分的不对劲！

我密文呢！它没有给我密文！😭

那我只好coppersmith了☝️🤓

Exp

import gmpy2
import sympy
from Crypto.Util.number import *
from mpmath.libmp.backend import sage_utils

e=65537
K =  3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704697742640442010893811830528349203606514981272974154582682489532205008927740716725904614810707240205595586894383039181983075907373556864396176123489201513001026708388504250801785422323131912494763394371589512367935031912074535458595633402462463667072692589863355712935552396330534658448628449816139943205511637
dp =  53589538487289875479012684116246778147274714450209576105277816626983528993595125486641833027290704077932308918237978477501981907543847383655230156916578979044682282870153618849419762148348930652564442177633668690473147864322377146889467662769284463217004314651469157455678363085510100707437896627192687923547

phi_K=3995906172915513953882445609459153360257793100017419734812726991957587919349807133880917342081892953635338598486012480314014321088548439223094566668968735207492741920107799674089668131177188073985125603237341660194741854181484934968528811686828555591685803851909027192343245722679639249600176791158349393704563491939855074908131201080601789660278277463091128258620162393005493660325529049372273750256050052601812762275558341459733334059173575187257879545301966909946591430521682456999675425592588401663829861424645503090962151175185283606430962734512615168075590554358536815875975156290442548837984467548691863947916
P=89706459192396530593549443920371512846107199328839237547229758327568121878195799315931797683572600269608687634404290962684155916188631860811034680949192525086238991914925741833782609688548028611711472171734508568556069872649373734405124829887118997365400928949792704456407061927794321219467125520582544212039
Q=44544241394539455087080003827042433390596610554187086515097380871947145536991877216409262767617552724165444473076549560658417398194657348107209262950353565993877966067642602951964287850776064487853037993132356275513691026700801254797314898063932907251598380047383415220014112316421578570998223070668797351683
x = 2636020992576559969055483957060200941734026828135579110378070592732862908176025649071069827089999996350015210043636523971348821850565913816154887832272305
y = 7886513101716991094728039196608717849158915101115291363845210343608904418304571443491051842715241903123031976527174063528298034452215971449949398656913945
phi = 115505961171763309547793530782914001823768056515083869218337105172209622283311582473506324170565971054492347897941697574972266679462737991988159654350224823122310342866537098903019067348499259894857405865405379172014292034138593409888061494667098647947191077373457924105640280156013690526621147715122416478264

d=inverse(e,phi_K)
def solve(a, b, c):
    D = b ** 2 - 4 * a * c
    # assert gmpy2.is_square(D)
    x1 = (-b + gmpy2.isqrt(D)) // (2 * a)
    x2 = (-b - gmpy2.isqrt(D)) // (2 * a)
    return x1, x2

a = x - 1
b = x * y - 1 + (x - 1) * (y - 1) - phi
c = (y - 1) * (x * y - 1)
k1, k2 = solve(a, b, c)
if (x * y - 1) % k1 == 0:
    k2 = (x * y - 1) // k1
elif (x * y - 1) % k2 == 0:
    k1, k2 = k2, (x * y - 1) // k2
else:
    assert False
p, q = x + k2, y + k1
n = p * q
PR.<m> = PolynomialRing(Zmod(n))
f = m^2 - (P+Q)*m + P*Q
x0 = f.small_roots()[0]
print(long_to_bytes(int(x0)))

#b'DASCTF{this_1s_crazy_Rsa}'

太Crazy了

为了终将忘却的纪念