rsa之wilson定理

Posted on

在近期的roarctf中，babyrsa涉及到大数阶乘取模的问题，记录一下wilson定理在rsa中的使用

题目给的信息如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sympy

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
    
A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e = 0x1001
c = 38347207883249601033653636821391847544875416880619614342339765883967916960100888999916613942668007089161071995631543462301367053958077198225214363505024848543179161424532987598516195302155764378892435582732218546342964613797538210260769612972831286966696915391991999466554505813797987381860855552244138180628982832282918799144636417921948189345110125610972711494191577055380771099863428248761761388282714659239444209955862537018724141881150316760288205511447144

在威尔逊定理中，对于质数p，有

1
2
3
(p-2)! mod p = 1
(p-1) mod p = -1
(p-1)! mod p = -1

解题思路就是使用wilson定理得到余数，之后使用得到的三个素数求出d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sympy
import gmpy2
import binascii

def wilson(x,y):
    a = 1
    while (y<=x-2):
        a *= y
        a %= x
        y += 1
    return a
A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e = 0x1001
c = 38347207883249601033653636821391847544875416880619614342339765883967916960100888999916613942668007089161071995631543462301367053958077198225214363505024848543179161424532987598516195302155764378892435582732218546342964613797538210260769612972831286966696915391991999466554505813797987381860855552244138180628982832282918799144636417921948189345110125610972711494191577055380771099863428248761761388282714659239444209955862537018724141881150316760288205511447144
x1 = wilson(A1,B1+1)
x2 = wilson(A2,B2+1)
y1 = gmpy2.invert(x1,A1)
y2 = gmpy2.invert(x2,A2)
p = sympy.nextprime(y1)
q = sympy.nextprime(y2)
r = n/q/p
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print binascii.a2b_hex(hex(m)[2:])