Content

更好的效果PDF:pdf文章列表 | Asiv's Blog (niceasiv.cn)

Factoring challenge #1:

Your goal in this project is to break RSA when the public modulus NN is generated incorrectly. This should serve as yet another reminder not to implement crypto primitives yourself.

Normally, the primes that comprise an RSA modulus are generated independently of one another. But suppose a developer decides to generate the first prime pp by choosing a random number RR and scanning for a prime close by. The second prime qq is generated by scanning for some other random prime also close to RR. We show that the resulting RSA modulus N=pqN=p q can be easily factored.

在公开的N没有被正确的生成时破解RSA。通常在RSA中构成模数N的素数q和p,应该独立生成。如果开发者使用一个随机数R,并选择R附近的两个素数作为q和p，那么这种情况情况下生成的RSA模数N就很容易被破解。

Suppose you are given a composite(合数) NN and are told that NN is a product of two relatively close primes pp and qq, namely pp and qq satisfy

∣p−q∣<2N1/4|p-q|<2 N^{1 / 4}

Your goal is to factor NN. Let AA be the arithmetic(算数) average of the two primes, that is A=p+q2A=\frac{p+q}{2}. Since pp and qq are odd(奇数), we know that p+qp+q is even and therefore AA is an integer(整数).

可以得到 A=p+q2<N14A=\frac{p+q}{2}<N^{\frac{1}{4}}

To factor NN you first observe that under condition ∗)\left.{ }^*\right) the quantity N\sqrt{N} is very close to AA. In particular, we show below that:

A−N<1∗{A-\sqrt{N}<1}*

But since AA is an integer, rounding N\sqrt{N} up to the closest integer reveals the value of AA. In code, A=A= ceil (sqrt⁡(N))(\operatorname{sqrt}(N)) where "ceil" is the ceiling function. Visually, the numbers p,q,Np, q, \sqrt{N} and AA are ordered as follows:

Since AA is the exact mid-point between pp and qq there is an integer xx such that p=A−xp=A-x and q=A+xq=A+x. But then N=pq=(A−x)(A+x)=A2−x2N=p q=(A-x)(A+x)=A^2-x^2 and therefore x=A2−Nx=\sqrt{A^2-N}.

Now, given xx and AA you can find the factors pp and qq of NN since p=A−xp=A-x and q=A+xq=A+x. You have now factored NN !

因为AA是pp,qq的中点

∴\therefore p=A−xp=A-x q=A+xq=A+x  ⟹  N=pq=(A−x)(A+x)=A2−x2\implies N=p q=(A-x)(A+x)=A^2-x^2

∴x=A2−N\therefore x=\sqrt{A^2-N}

所以得到xx的值可以得到p,qp,q的取值

Further reading: the method described above is a greatly simplified version of a much more general result on factoring when the high order bits of the prime factor are known.

In the following challenges, you will factor the given moduli using the method outlined above. To solve this assignment it is best to use an environment that supports multi-precision arithmetic and square roots. In Python you could use the gmpy2 module. In C you can use GMP.

The following modulus NN is a products of two primes pp and qq where ∣p−q∣<2N1/4∗|p-q|<2 N^{1 / 4}*. Find the smaller of the two factors and enter it as a decimal integer in the box below.

1
2
3
4
5
N = 17976931348623159077293051907890247336179769789423065727343008115 \
77326758055056206869853794492129829595855013875371640157101398586 \
47833778606925583497541085196591615128057575940752635007475935288 \
71082364994994077189561705436114947486504671101510156394068052754 \
0071584560878577663743040086340742855278549092581

For completeness, let us see why A−N<1A-\sqrt{N}<1. This follows from the following simple calculation. First observe that A2−N=(p+q2)2−N=p2+2N+q24−N=p2−2N+q24=(p−q)2/4A^2-N=\left(\frac{p+q}{2}\right)^2-N=\frac{p^2+2 N+q^2}{4}-N=\frac{p^2-2 N+q^2}{4}=(p-q)^2 / 4. Now, since for all x,y:(x−y)(x+y)=x2−y2x, y: \quad(x-y)(x+y)=x^2-y^2 we obtain A−N=(A−N)A+NA+N=A-\sqrt{N}=(A-\sqrt{N}) \frac{A+\sqrt{N}}{A+\sqrt{N}}= A2−NA+N=(p−q)2/4A+N\frac{A^2-N}{A+\sqrt{N}}=\frac{(p-q)^2 / 4}{A+\sqrt{N}} Since N≤A\sqrt{N} \leq A it follows that A−N≤(p−q)2/42N=(p−q)28NA-\sqrt{N} \leq \frac{(p-q)^2 / 4}{2 \sqrt{N}}=\frac{(p-q)^2}{8 \sqrt{N}}. By assumption (*) we know that (p−q)2<4N(p-q)^2<4 \sqrt{N} and therefore A−N≤4N8N=1/2A-\sqrt{N} \leq \frac{4 \sqrt{N}}{8 \sqrt{N}}=1 / 2 as required.

0<A−N<10<A-\sqrt{N}<1  ⟹  A<N+1\implies A<\sqrt{N}+1

proof:\text{proof:}

A=p+q2, N=pq{A}=\frac{p+q}{2}, {~N}={pq} AA为整数

对左边:

0<A−N0<{A}-\sqrt{N} : 由基本不等式 ab≤a+b2\sqrt{ab}\leq\frac{a+b}{2} 可以得到 pq<p+q2\sqrt{pq}<\frac{p+q}{2} 因为 p≠qp\neq q ，所以无法取到等号，所以 pq<A\sqrt{pq}<{A}  ⟹  0<A−N\implies 0<A-\sqrt{N}  ⟹  N<A\implies\sqrt{N}<{A}

对右边:

A−N<1A-\sqrt{N}<1,有:

A2−N=(p+q2)2−N=p2+2 N+q24−N=p2−2 N+q24=(p−q)24(1)\mathrm{A}^2-\mathrm{N}=\left(\frac{\mathrm{p}+\mathrm{q}}{2}\right)^2-\mathrm{N}=\frac{\mathrm{p}^2+2 \mathrm{~N}+\mathrm{q}^2}{4}-\mathrm{N}=\frac{\mathrm{p}^2-2 \mathrm{~N}+\mathrm{q}^2}{4}=\frac{(\mathrm{p}-\mathrm{q})^2}{4}\tag{1}

对于 A−NA-\sqrt{N} ，有:

A−N=(A−N)(A+N)A+N=A2−NA+N=A+N=(p−q)24A+N(1)A-\sqrt{N}=\frac{(A-\sqrt{N})(A+\sqrt{N})}{A+\sqrt{N}}=\frac{A^2-N}{A+\sqrt{N}}={A+\sqrt{N}}=\frac{\frac{(p-q)^2}{4}}{A+\sqrt{N}} \tag{1}

由于 N<A\sqrt{N}<A ，那么，

A−N=(p−q)24 A+N<(p−q)24N+N=(p−q)28N(3)A-\sqrt{\mathrm{N}}=\frac{\frac{(\mathrm{p}-\mathrm{q})^2}4}{\mathrm{~A}+\sqrt{\mathrm{N}}}<\frac{\frac{(\mathrm{p}-\mathrm{q})^2}4}{\sqrt{\mathrm{N}}+\sqrt{\mathrm{N}}}=\frac{(\mathrm{p}-\mathrm{q})^2}{8 \sqrt{\mathrm{N}}} \tag{3}

由于challenge #1满足 ∣p−q∣<2N1/4|p-q|<2 N^{1 / 4} ，即 (p−q)2<4N(p-q)^2<4 \sqrt{N} ，最后得到:

A−N=(p−q)28N<4N8N=1/2<1(4)\mathrm{A}-\sqrt{\mathrm{N}}=\frac{(\mathrm{p}-\mathrm{q})^2}{8 \sqrt{\mathrm{N}}}<\frac{4 \sqrt{\mathrm{N}}}{8 \sqrt{\mathrm{N}}}=1 / 2<1 \tag{4}

Enter the answer for factoring challenge #1 in the box below:

1
13407807929942597099574024998205846127479365820592393377723561443721764030073662768891111614362326998675040546094339320838419523375986027530441562135724301

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2

def task1():
    #初始化大整数n
    n =gmpy2.mpz('17976931348623159077293051907890247336179769789423065727343008115' + 
            '77326758055056206869853794492129829595855013875371640157101398586' +
            '47833778606925583497541085196591615128057575940752635007475935288' +
            '71082364994994077189561705436114947486504671101510156394068052754' +
            '0071584560878577663743040086340742855278549092581')
    #得到n的平方根的整数部分
    A,r=gmpy2.isqrt_rem(n)#A为整数部分，r为余数
    if r>0:
        A+=1
    #得到x
    x=gmpy2.isqrt(A**2-n)
    #得到p和q
    p,q=A-x,A+x
    #检验p和q是否为素数且p*q=n
    if gmpy2.is_prime(p) and gmpy2.is_prime(q) and gmpy2.mul(p,q)==n:
        print('p=',p)
        print('q=',q)
    
if __name__ == '__main__':
    task1()

Factoring challenge #2:

The following modulus NN is a products of two primes pp and qq where ∣p−q∣<211N1/4|p-q|<2^{11} N^{1 / 4}. Find the smaller of the two factors and enter it as a decimal integer.

Hint: in this case A−N<220A-\sqrt{N}<2^{20} so try scanning for AA from N\sqrt{N} upwards, until you succeed in factoring NN.

Proof:\text{Proof:}

由Factoring challenge #1的证明

A=p+q2, N=pq{A}=\frac{p+q}{2}, {~N}={pq} AA为整数

∣p−q∣<211N1/4|p-q|<2^{11} N^{1 / 4}  ⟹  \implies(p−q)2<222N(p-q)^2<2^{22}\sqrt{N}

由公式33可以得到

0<A−N=(p−q)24 A+N<(p−q)24N+N=(p−q)28N<222N8N=219(5)0<A-\sqrt{\mathrm{N}}=\frac{\frac{(\mathrm{p}-\mathrm{q})^2}4}{\mathrm{~A}+\sqrt{\mathrm{N}}}<\frac{\frac{(\mathrm{p}-\mathrm{q})^2}4}{\sqrt{\mathrm{N}}+\sqrt{\mathrm{N}}}=\frac{(\mathrm{p}-\mathrm{q})^2}{8 \sqrt{\mathrm{N}}}<\frac{2^{22}\sqrt{N}}{8\sqrt{N}}=2^{19}\tag{5}

因此AA的范围应该在(N,219+N)(\sqrt{N},2^{19}+\sqrt{N})

1
2
3
4
5
N =6484558428080716696628242653467722787263437207069762630604390703787 \
9730861808111646271401527606141756919558732184025452065542490671989 \
2428844841839353281972988531310511738648965962582821502504990264452 \
1008852816733037111422964210278402893076574586452336833570778346897 \
15838646088239640236866252211790085787877

Enter the answer for factoring challenge #2 in the box below:

1
25464796146996183438008816563973942229341454268524157846328581927885777969985222835143851073249573454107384461557193173304497244814071505790566593206419759

Code

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
import gmpy2

def task2():
    #初始化大整数n
    n =gmpy2.mpz('6484558428080716696628242653467722787263437207069762630604390703787'+'9730861808111646271401527606141756919558732184025452065542490671989'+
                  '2428844841839353281972988531310511738648965962582821502504990264452'+'1008852816733037111422964210278402893076574586452336833570778346897 '+'15838646088239640236866252211790085787877')
    #初始化得到n的平方根的整数部分
    A=gmpy2.isqrt(n)+1#A为整数部分 向上取整A^2>n
    #循环次数
    max_count=pow(2,20)
    #得到x
    for i in range(max_count):
        x,r=gmpy2.isqrt_rem(A**2-n)
        #得到p和q
        if r==0:
            p,q=A-x,A+x
            #检验p和q是否为素数且p*q=n
            if gmpy2.is_prime(p) and gmpy2.is_prime(q) and gmpy2.mul(p,q)==n:
                print('[!] Found it count=',i)
                print('p=',p)
                print('q=',q)
                break
        A+=1

if __name__ == '__main__':
    task2()

Factoring challenge #3:

The following modulus NN is a product of two primes pp and qq where ∣3p−2q∣<N1/4|3 p-2 q|<N^{1 / 4}. Find the smaller of the two factors and enter it as a decimal integer. Hint: first show that 6N\sqrt{6 N} is close to 3p+2q2\frac{3 p+2 q}{2} and then adapt the method in challenge #1 to factor NN.

1
2
3
4
5
N =72006226374735042527956443552558373833808445147399984182665305798191 \
63556901883377904234086641876639384851752649940178970835240791356868 \
77441155132015188279331812309091996246361896836573643119174094961348 \
52463970788523879939683923036467667022162701835329944324119217381272 \
9276147530748597302192751375739387929

A−6N<186A-\sqrt{6N}<\frac{1}{8\sqrt{6}}

Proof:\text{Proof:}

定义A=3p+2q2A=\frac{3p+2q}{2}即AA是3p3p和2q2q的中点，且3p3p是奇数,2q2q是偶数，所以AA一定不是整数

由challenge #1同理

$\because $$\text{A是3p,2q的中点}$

∴\therefore p=A−x3p=\frac{A-x}{3} q=A+x2q=\frac{A+x}{2}  ⟹  N=pq=(A−x)(A+x)6=A2−x26\implies N=p q=\frac{(A-x)(A+x)}{6}=\frac{A^2-x^2}{6}(这里其实A−x3\frac{A-x}{3}有可能为p或者q,还要根据A−xA-x是否被3除尽就可确定)

∴x=A2−6N\therefore x=\sqrt{A^2-6N}

所以得到xx的值可以得到p,qp,q的取值

由ab<=a+b2\sqrt{ab}<=\frac{a+b}{2}

∴6pq<3p+2q2\therefore{\sqrt{6pq}<\frac{3p+2q}{2}}  ⟹  6N<A\implies \sqrt{6N}<A

A−6N=A2−6NA+6N=(3p−2q)24A+6N<(3p−2q)246N+6N=(3p−2q)2426N(6)A-\sqrt{6N}=\frac{A^2-6N}{A+\sqrt{6N}}=\frac{\frac{(3p-2q)^2}{4}}{A+\sqrt{6N}}<\frac{\frac{(3p-2q)^2}{4}}{\sqrt{6N}+\sqrt{6N}}=\frac{\frac{(3p-2q)^2}{4}}{2\sqrt{6N}} \tag {6}

由于challenge3满足∣3p−2q∣<N1/4|3 p-2 q|<N^{1 / 4}即是(3p−2q)2<N(3p-2q)^2<\sqrt{N}

A−6N<(3p−2q)2426N<186A-\sqrt{6N}<\frac{\frac{(3p-2q)^2}{4}}{2\sqrt{6N}}<\frac{1}{8\sqrt{6}}

Enter the answer for factoring challenge #3 in the box below:

1
21909849592475533092273988531583955898982176093344929030099423584127212078126150044721102570957812665127475051465088833555993294644190955293613411658629209

code

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
30
31
32
33
34
from decimal import Decimal, getcontext

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def task3():
   
    n=720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929
    getcontext().prec=350#设置精度
    A=Decimal(isqrt(6*n))+Decimal(0.5)
    while True:
        x=Decimal(A**2-6*Decimal(n)).sqrt()
        p=int(A-x)
        q=int(A+x)
        if p*q==6*n:
            if p%3==0 and q%2==0:
                p//=3
                q//=2
                break
            if p%2==0 and q%3==0:
                p//=2
                q//=3
                break
        A+=1
    print(p)
    print(q)
if __name__ == '__main__':
    task3()

4.

The challenge ciphertext provided below is the result of encrypting a short secret ASCII plaintext using the RSA modulus given in the first factorization challenge.

The encryption exponent used is e=65537e=65537 The ASCII plaintext was encoded using PKCS v1.5 before the RSA function was applied, as described in PKCS.

Use the factorization you obtained for this RSA modulus to decrypt this challenge ciphertext and enter the resulting English plaintext in the box below. Recall that the factorization of NN enables you to compute φ(N)\varphi(N)from which you can obtain the RSA decryption exponent.

1
2
Challenge ciphertext (as a decimal integer):
22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540

After you use the decryption exponent to decrypt the challenge ciphertext you will obtain a PKCS1 encoded plaintext.To undo the encoding it is best to write the decrypted value in hex.You will observe that the number starts with a '0x02' followed by many random non-zero digits.Look for the '0x00' separator and the digits following this separator are the ASCII letters of the plaintext.

(note: the separator used here is '0x00', not '0xFF' as stated in the lecture)

1
2
3
4
5
公钥就是 N，e 而 私钥就是N，d
加密
m^e ≡ c (mod n)
解密
c^d ≡ m (mod n)
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
30
31
32
33
import binascii
import gmpy2
def task4():
    c = gmpy2.mpz('22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256' +
            '46583996794288946076454204058156474898801373486412045232522932017648791666640299750918872997169052608322206777160001932' + 
            '9260870009579993724077458967773697817571267229951148662959627934791540')

    n = gmpy2.mpz('17976931348623159077293051907890247336179769789423065727343008115' + 
            '77326758055056206869853794492129829595855013875371640157101398586' +
            '47833778606925583497541085196591615128057575940752635007475935288' +
            '71082364994994077189561705436114947486504671101510156394068052754' +
            '0071584560878577663743040086340742855278549092581')

    e =gmpy2.mpz(65537)

    a = gmpy2.isqrt(n) + 1
    x = gmpy2.isqrt(a**2 - n)

    p = a - x
    q = a + x

    fi = (p-1) * (q-1)#欧拉函数

    d = gmpy2.invert(e, fi)#求e的模fi的逆元

    r = gmpy2.powmod(c, d, n)#求c的d次方模n
    #PKCS解密
    m = gmpy2.digits(r, 16).split('00')[1]#将r转换为16进制，然后以00为分隔符分割，取第二个元素
    
    return binascii.unhexlify(m.encode('utf-8'))

if __name__ == '__main__':
    print(task4())
1
Factoring lets us break RSA.

参考博客

实验四 RSA中公开的模数N_chuxuezheerer的博客-CSDN博客_rsa 模数