2023ciscn badkey1&baykey2

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\\ let\ q-1已知(随机生成)\\ let\ A=q-1\\ \frac{A*a-1}{A*a-k*e}=p$$ $$其中A*a-k*e是A*a-1的因子\\ 这里考虑a<e的情况，p很大，所以A*a-k*e是小因子\\ 且A*a-k*e<e\\ 使用A*a\ mod\ e代替$$ $$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循环生成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-1
    for i in range(e):
        if a*i%e==0:
            continue
        if 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*q
                d = 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 == 0
        assert n not in used_n
        used_n.append(n)
        q = n // p
        assert q > 0
        assert q != p
        assert q.bit_length() == 512
        assert isPrime(q)
        assert q % e != 1
        d = 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.d
        if hasattr(input_comps, 'q'):
            p = input_comps.p
            q = input_comps.q
        else:
            # 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 = ktot
            while 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, 1979
            spotted = False
            a = Integer(2)
            while not spotted and a < 100:
                k = Integer(t)
                # Cycle through all values a^{t*2^i}=a^k
                while 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 = True
                        break
                    k *= 2
                # This value was not any good... let's try another!
                # print(a)
                # print(a)
                a += 2

            if 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的原理。

链接文章 rsa中已知 n,e,d 来分解n_rsa分解n_前方是否可导？的博客-CSDN博客](https://blog.csdn.net/weixin_44110537/article/details/107869682))

$$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+3)//4==0\\ so\ i=2\\ for\ a\ in\ range(2,100,2):if \ a^{phi//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^k
                while 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 = True
                        break
                    k *= 2
                # This value was not any good... let's try another!
                # print(a)
                # print(a)
                a += 2

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

下面是重点：

源码分解取的g是2到100间的偶数。要使他们在环n中满足

$$g^{phi//4}=-1 \ or\ 1$$

只需要

$$factor(g)=2*a*b...\\ 2^{phi//4}==1\ or\ -1\\ a^{phi//4}==1\ or\ -1\\ b^{phi//4}==1\ or\ -1\\ ...$$

很显然只需要小于50的所有素数满足

$$prime_i^{phi//4}=1\ or\ -1\mod n$$

我们可以计算一下任意一个数满足上面等式的概率

$$g^{p-1//2}=1\mod p$$

	1/2	1/2
1/2	$g^{(p-1)//2}=1\mod p$ (A)	$g^{(p-1)//2}=-1\mod p$ (B)
1/2	$g^{(q-1)//2}=1\mod q$ (C)	$g^{(q-1)//2}=-1\mod q$ (D)

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

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

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

满足上面情况的概率是

$$\frac{1}{2^{15}}=\frac{1}{32768}$$

也就是生成33000个素数是有很大概率找到满足条件的q

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

优化：

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

p是给定的，使用可以先计算15个素数在p的是否二次剩余结果。

再对生成的q，依次每个素数继续判断是否等于上述由p生成的结果。

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

10s内遍历3000个素数，进程多开，获取多组结果。可以求解。

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 False
    return True

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 False
    return True

p = 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*i
    try:
        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+=1
    q=gmpy2.next_prime(q)
    while (q-1)%4==0:
        q=gmpy2.next_prime(q)
    # print(q)
    n=p*q
    if 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个结果，找到一个解

---