BUUCTF 每日打卡 2021-4-26

引言

一道 babyRSA 搞了一晚上[捂脸] 因为一些 sb 错误

babyRSA

加密代码如下：

import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

三元的 RSA 就没解出来过[捂脸] 参考博客：https://www.cnblogs.com/jane315/p/13805724.html 看到阶乘，没想到威尔逊定理 p,q,r = nextPrime((B!)%A) 先上威尔逊定理： 若 \(p\) 是素数，则 \[ (p-1)! \equiv -1 \space mod \space p \] 有加密代码可得 \(A\) 是素数，且 \(B\) 小于 \(A\) 方法一： \[ p(B+1)(B+2)\cdots(A-1) \equiv (A-1)! \equiv -1 \space mod \space A \] 即 \[ p[-(B+1)(B+2)\cdots(A-1)]\equiv 1 \space mod \space A \] 即 \(p\) 是 \(-(B+1)(B+2)\cdots(A-1)\) 模 \(A\) 的逆元 求 \(p,q\) 的函数如下：

def get(a, b): # 求p,q
    k = 1
    for i in range(b+1, a):
        k *= i
        k %= a
    return next_prime((-inverse(k, a))%a)

方法二： 利用威尔逊定理的推论： \[ (p-2)! \equiv 1 \space mod \space p \] 推理过程如下： 来源于 wiki 求 \(p,q\) 的函数如下：

def get(a, b): # 求p,q
    k = 1
    for i in range(b+1, a-1):
        k *= i
        k %= a
    return next_prime(inverse(k, a))

解密代码如下：

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

A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e = int('0x1001', 16)
c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

def get(a, b): # 求p,q

p = get(A1, B1)
q = get(A2, B2)
r = (n // p) // q
phi = (p-1)*(q-1)*(r-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

get 函数忘记加 next_prime 然后搞了半天[捂脸]

结语

早点睡了 希望继续坚持