文章目录

• • badkey1
  • badkey2

badkey1

RSA源码审计可用点

if Integer(n).gcd(d) != 1:raise ValueError("RSA private exponent is not coprime to modulus")

写成表达式
k ∗ p ∗ e = a ∗ ( p − 1 ) ∗ ( q − 1 ) + 1 l e t q − 1 已知 ( 随机生成 ) l e t A = q − 1 A ∗ a − 1 A ∗ a − k ∗ e = p k*p*e=a*(p-1)*(q-1)+1\\ let\ q-1已知(随机生成)\\ let\ A=q-1\\ \frac{A*a-1}{A*a-k*e}=p k∗p∗e=a∗(p−1)∗(q−1)+1let q−1已知(随机生成)let A=q−1A∗a−k∗eA∗a−1​=p

其中 A ∗ a − k ∗ e 是 A ∗ a − 1 的因子 这里考虑 a < e 的情况， p 很大，所以 A ∗ a − k ∗ e 是小因子 且 A ∗ a − k ∗ e < e 使用 A ∗ a m o d e 代替 其中A*a-k*e是A*a-1的因子\\ 这里考虑a<e的情况，p很大，所以A*a-k*e是小因子\\ 且A*a-k*e<e\\ 使用A*a\ mod\ e代替 其中A∗a−k∗e是A∗a−1的因子这里考虑a<e的情况，p很大，所以A∗a−k∗e是小因子且A∗a−k∗e<e使用A∗a mod e代替

w h i l e 1 : g e n e r a t e q , A = q − 1. f o r a i n r a n g e ( 0 , e ) : p = A ∗ a − 1 A ∗ a m o d e i s P r i m e ( p ) a n d p . b i t s = 512 : b r e a k while\ 1:\\ generate\ q,A=q-1.\\ for\ a\ in\ range(0,e):\\ p=\frac{A*a-1}{A*a\mod e}\\ isPrime(p)\ and\ p.bits=512:break while 1:generate q,A=q−1.for a in range(0,e):p=A∗amodeA∗a−1​isPrime(p) and p.bits=512:break

后面使用while循环生成q的同时爆破a，对于a爆破（0,e)就好

exp

from Crypto.Util.number import *
from pwn import *
context.log_level='debug'
from hashlib import sha256
p=remote('47.94.206.10',39984)
from tqdm import *
print(string.ascii_letters)
def proof():p.recvuntil(b'sha256(XXXX+')temp=p.recvuntil(b') == ',drop=True)h=p.recvuntil(b'\n',drop=True)print(temp,h)for i in tqdm(string.ascii_letters+string.digits):for j in string.ascii_letters+string.digits:for m in string.ascii_letters+string.digits:for n in string.ascii_letters+string.digits:temp1=(i+j+m+n).encode()+temp# print(temp)if sha256(temp1).hexdigest()==h.decode():print('true')p.sendline((i+j+m+n).encode())return
proof()
pp=12510875347176235686997812103317869460948038516680558933190808704266569039260784999860406852809645040121612396013734331543157989801627761134198090682817857
qq=7333254708337403375133788300619379627444747520722960530311097998509786409312055064698519936360202960226160296457194092174813082331974217099658032007084301
p.recvuntil(b'p = ')
p.sendline(str(pp).encode())
p.recvuntil(b'q = ')
p.sendline(str(qq).encode())
p.interactive()

生成p,q的代码

e=65537
while 1:p=getPrime(512)a=p-1for i in range(e):if a*i%e==0:continueif gcd((a*i%e),a*i-1)==(a*i%e):q=(a*i-1)//(a*i%e)if isPrime(q) and q.bit_length()==512:print(p,q)n=p*qd = inverse(e, (p-1)*(q-1))RSA.construct([n,e,d,p,q])break

badkey2

题目

e = 65537
p = getPrime(512)
while p % e == 1:p = getPrime(512)
signal.alarm(10)
print("Give me 10 bad RSA keypairs that have the same prime factor:", p)used_n = []
for i in range(10):try:n = int(input('n = '))assert n % p == 0assert n not in used_nused_n.append(n)q = n // passert q > 0assert q != passert q.bit_length() == 512assert isPrime(q)assert q % e != 1d = inverse(e, (p-1)*(q-1))except:print("Invalid n")exit(2)try:key = RSA.construct([n,e,d])print("This is not a bad RSA keypair,")exit(3)except KeyboardInterrupt:print("Hacker detected.")exit(4)except ValueError:print("Good job!")print("How could this happen?")
from secret import flag
print(flag)

同样是源码审计，关键代码处

if not hasattr(input_comps, 'd'):key = RsaKey(n=n, e=e)else:d = input_comps.dif hasattr(input_comps, 'q'):p = input_comps.pq = input_comps.qelse:# Compute factors p and q from the private exponent d.# We assume that n has no more than two factors.# See 8.2.2(i) in Handbook of Applied Cryptography.ktot = d * e - 1# The quantity d*e-1 is a multiple of phi(n), even,# and can be represented as t*2^s.t = ktotwhile t % 2 == 0:t //= 2# print('t',t)# Cycle through all multiplicative inverses in Zn.# The algorithm is non-deterministic, but there is a 50% chance# any candidate a leads to successful factoring.# See "Digitalized Signatures and Public Key Functions as Intractable# as Factorization", M. Rabin, 1979spotted = Falsea = Integer(2)while not spotted and a < 100:k = Integer(t)# Cycle through all values a^{t*2^i}=a^kwhile k < ktot:cand = pow(a, k, n)# print(pow(cand, 2, n) == 1)# Check if a^k is a non-trivial root of unity (mod n)if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:# We have found a number such that (cand-1)(cand+1)=0 (mod n).# Either of the terms divides n.p = Integer(n).gcd(cand + 1)spotted = Truebreakk *= 2# This value was not any good... let's try another!# print(a)# print(a)a += 2if not spotted:raise ValueError("Unable to compute factors p and q from exponent d.")

RSA.construct([n, e, d])

这里只有n,e,d，没有p,q所以会跳到下面的else。其他的报错点基本没用，gcd(n,d)!=1这个在第一题里面考过想必不会再考。

首先要了解已知e,d分解n的原理。

文章
g e d − 1 = 1 , k = e d − 1 g k − 1 = ( g k / 2 − 1 ) ∗ ( g k / 2 + 1 ) m o d n i f g k / 2 − 1 ! = 0 a n d g k / 2 + 1 ! = 0 : f a c t o r ( n ) g k / 2 − 1 c a n c o n t i n u e p h i = t ∗ 2 i l e t p , q i s ( P + 1 ) / / 4 = = 0 s o i = 2 f o r a i n r a n g e ( 2 , 100 , 2 ) : i f a p h i / / 4 = 1 o r − 1 , c a n ′ t f a c t o r ( n ) g^{ed-1}=1,k=ed-1\\ g^k-1=(g^{k/2}-1)*(g^{k/2}+1)\mod n\\ if\ g^{k/2}-1!=0\ and\ g^{k/2}+1!=0:factor(n)\\ g^{k/2}-1\ can\ continue\\ phi=t*2^i\\ let\ p,q\ is\ (P+1)//4==0\\ so\ i=2\\ for\ a\ in\ range(2,100,2):if \ a^{phi//4}=1\ or-1,can't\ factor(n) ged−1=1,k=ed−1gk−1=(gk/2−1)∗(gk/2+1)modnif gk/2−1!=0 and gk/2+1!=0:factor(n)gk/2−1 can continuephi=t∗2ilet p,q is (P+1)//4==0so i=2for a in range(2,100,2):if aphi//4=1 or−1,can′t factor(n)

while not spotted and a < 100:k = Integer(t)# Cycle through all values a^{t*2^i}=a^kwhile k < ktot:cand = pow(a, k, n)# print(pow(cand, 2, n) == 1)# Check if a^k is a non-trivial root of unity (mod n)if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:# We have found a number such that (cand-1)(cand+1)=0 (mod n).# Either of the terms divides n.p = Integer(n).gcd(cand + 1)spotted = Truebreakk *= 2# This value was not any good... let's try another!# print(a)# print(a)a += 2

上面这块自己多看看，网上原理解释的多着勒

下面是重点：

源码分解取的g是2到100间的偶数。要使他们在环n中满足
g p h i / / 4 = − 1 o r 1 g^{phi//4}=-1 \ or\ 1 gphi//4=−1 or 1
只需要
f a c t o r ( g ) = 2 ∗ a ∗ b . . . 2 p h i / / 4 = = 1 o r − 1 a p h i / / 4 = = 1 o r − 1 b p h i / / 4 = = 1 o r − 1 . . . factor(g)=2*a*b...\\ 2^{phi//4}==1\ or\ -1\\ a^{phi//4}==1\ or\ -1\\ b^{phi//4}==1\ or\ -1\\ ... factor(g)=2∗a∗b...2phi//4==1 or −1aphi//4==1 or −1bphi//4==1 or −1...
很显然只需要小于50的所有素数满足
p r i m e i p h i / / 4 = 1 o r − 1 m o d n prime_i^{phi//4}=1\ or\ -1\mod n primeiphi//4​=1 or −1modn
我们可以计算一下任意一个数满足上面等式的概率
g p − 1 / / 2 = 1 m o d p g^{p-1//2}=1\mod p gp−1//2=1modp

当AC或者BD出现时满足上面式子，AD,BC出现不满足。（自己可以写代码试一试）

即对每个数，有1/2的可能满足，所有2到50一共15个素数

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

满足上面情况的概率是
1 2 15 = 1 32768 \frac{1}{2^{15}}=\frac{1}{32768} 2151​=327681​
也就是生成33000个素数是有很大概率找到满足条件的q

生成3000个也有大概10%的概率找到一个q。

优化：

直接使用getPrime()函数生成512素数太慢了。使用gmpy2的next_prime代替。

p是给定的，使用可以先计算15个素数在模p的二次剩余和二次非剩余。

再对生成的q，依次每个素数进行二次剩余判断是否等于上述由p生成的结果。

对pow函数，使用gmpy2.powmod()函数替代

exp

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from pwn import *
from sympy import nextprime
import gmpy2
e = 65537
y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]def the_order(phi, n):for i in y:if pow(i, phi // 4, n) != 1 and pow(i, phi // 4, n) != n - 1:return Falsereturn Truedef new_j(q):for i,j in zip(y,qurd):if gmpy2.powmod(i,(q-1)//2,q)!=j and (gmpy2.powmod(i,(q-1)//2,q)-q)!=j:return Falsereturn Truep = 10504439101028664660056785533759761989088172436818960343147332749877720113462493129457363760368927072119588571013756543758997202324469792864400112417216047
qurd=[]
for i in y:if pow(i,(p-1)//2,p)==1:qurd.append(1)else:qurd.append(-1)
#下面是我已经找到的一些解
q = [12941445952388271518501756052187011501149499405168871440740910983587444166758145638747983510693930985198611865987273890258362827292141887844321565302715167,13331340306630130632668295656287107871517200264928668178560258006455071414325214985671123108479969251649736161940966364680698677632149263463624078927408023,7434749292102457006806028905956300543802343309461078048043254784168801223420316278052344606710502595254921038363421407101671516522244532611045003295946327,11890409393719017428826746031529522511702108519519988991626127567700592749109448482192996138745563686861491040026308935700133966439960052967280078213491223,12094689984134957547999803262855914414769454801965823112591686665694489791426019652663923493412725161510838415526513885922802598797054279454614070190610647,8312683912123787445374745935954752950118979295974508463977560704132674342154607799632011674489957072006007963119710237246105506104613247726875195578361487,12400983895223684533295037506453462964523981567289739456700770289624685689767428392042068167419707479466810080703087508448782504371547866119057602182365543,9239611150884101380010270524076721469903671396858138633200589273674800677797448403758231467635502406504335152314887188454728232761046216225222069851991183,10406762411752496134569102116243476673685791553223602413823061321535980066882136219630826271673775265409346346583771428390397397572542310484182406462859583,8735423512925567382151910965101795971352363586798572095418396512045770841639141112337897020112899066136897666947156134330548105970258198099327792405157647,9886818365906641873221553238917195355478636246811928665300629399133053405551992608688549378012227830243145920322961044585283900419548704642207044451904687]for i in q:n=p*itry:d = inverse(e, (p - 1) * (i - 1))RSA.construct([n, e, d])except:print("TRUE")
#验证部分结束
#关键部分如下
st=time.time()
i=1
q=0b1<<511
print(q.bit_length())
while 1:#随机跳跃取值if random.random()>0.6:q=q+2**random.randint(200,300)if i%1000==0:print(i)i+=1q=gmpy2.next_prime(q)while (q-1)%4==0:q=gmpy2.next_prime(q)# print(q)n=p*qif new_j(q):print('find')print('p=',p)print('q=',q)d = inverse(e, (p-1)*(q-1))try:RSA.construct([n,e,d])except:print(time.time()-st)break

output示例

512
1000
2000
find
p= 10504439101028664660056785533759761989088172436818960343147332749877720113462493129457363760368927072119588571013756543758997202324469792864400112417216047
q= 6703903964971298549787012499102923063739682910296196688861780773154167769700571554512674915212042448594411695416399727778548935735790753939350691161926863
8.528871774673462

8.5秒遍历3000个结果，找到一个解

上述是给定一个 p 找到一个解，题目要求是 10 s 内找到 10 个解 \color{red}{上述是给定一个p找到一个解，题目要求是10s内找到10个解} 上述是给定一个p找到一个解，题目要求是10s内找到10个解
这样写肯定是不行的，可以先本地生成 2 15 10 个解 \color{red}{这样写肯定是不行的，可以先本地生成2^{15}10个解} 这样写肯定是不行的，可以先本地生成21510个解
即对 2 15 个结果，在本地每个解先生成 10 个结果 \color{red}{即对2^{15}个结果，在本地每个解先生成10个结果} 即对215个结果，在本地每个解先生成10个结果
然后对于给定 p 在 2 1 5 之 中找到对应的 10 个 q 即可 \color{red}{然后对于给定p在2^15^之中找到对应的10个q即可} 然后对于给定p在215之中找到对应的10个q即可
实际上不用每个都生成10个解，毕竟是概率问题。
不明白的可以私信我
本地生成字典代码

from Crypto.Util.number import *
import time
import random
import gmpy2
y=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]qurd=[]
for i in y:if pow(i,(p-1)//2,p)==1:qurd.append(1)else:qurd.append(-1)
# print(len(y),len(x))
assert len(x)==len(y)
def new_j(q):for i,j in zip(y,qurd):if gmpy2.powmod(i,(q-1)//2,q)!=j and (gmpy2.powmod(i,(q-1)//2,q)-q)!=j:return Falsereturn True
def leg(p):res=[]for i in y:if gmpy2.powmod(i,(p-1)//2,p)==1:res.append(1)else:res.append(-1)return str(res)
q=0b1<<511
count=1
while 1:if random.random()>0.6:q=q+2**random.randint(200,300)q=gmpy2.next_prime(q)while (q-1)%4==0:q=gmpy2.next_prime(q)temp=leg(q)try:if len(data[temp])>=10:count-=1else:data[temp].append(q)except:data[temp]=[q]count+=1if count%1000==0:print(count)if count==2^15*10:break

查看当前生成的碰撞字典长度为10的个数，这里有2万个就足够了。

count=0
for i in data:if (len(data[i]))==10:count+=1
count

最终交互的exp

# -*- coding utf-8 -*-
# @Time : 2023/5/30 11:00from pwn import *import gmpy2
from gmpy2 import mpzfrom tqdm import tqdmcontext.log_level = 'debug'
from hashlib import sha256e = 65537
y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]def leg(p):res=[]for i in y:if gmpy2.powmod(i,(p-1)//2,p)==1:res.append(1)else:res.append(-1)return str(res)def proof(io):io.recvuntil(b'sha256(XXXX+')temp = io.recvuntil(b') == ', drop=True)h = io.recvuntil(b'\n', drop=True)print(temp, h)for i in tqdm(string.ascii_letters + string.digits):for j in string.ascii_letters + string.digits:for m in string.ascii_letters + string.digits:for n in string.ascii_letters + string.digits:temp1 = (i + j + m + n).encode() + temp# print(temp)if sha256(temp1).hexdigest() == h.decode():print('true')io.sendline((i + j + m + n).encode())returndic=eval(open('./res.txt',).read())
while 1:io=remote('node4.anna.nssctf.cn',28204)proof(io)io.recvuntil(b'factor: ')p=int(io.recvuntil(b'\n',drop=True))if (p-1)%4!=0:temp=leg(p)if len(dic[temp])==10:for i in range(10):io.recvuntil(b'n = ')io.sendline(str(dic[temp][i]*p).encode())io.recvuntil(b'job!\n')breakelse:continue

本文链接：https://my.lmcjl.com/post/2020.html