cryptography/programming_assignment_week6.py at master · vhborges/cryptography · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from gmpy2 import mpz, isqrt, ceil, floor, sqrt, get_context, invert, powmod

get_context().precision = 9999

def ex1():
    N = mpz(179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581)
    A = mpz(ceil(sqrt(N)))
    x = isqrt(A**2 - N)
    p = A - x
    q = A + x
    print(p)
    return p, q, N

def ex2():
    N = mpz(648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877)

    A = ceil(sqrt(N))
    i = 1
    while (A - sqrt(N)) < 2**20:
        A = mpz(ceil(sqrt(N)+i))
        x = isqrt(A**2 - N)
        p = A - x
        q = A + x
        if p*q == N:
            break
        i += 1
    print(p)

def ex3():
    N = mpz(720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929)
    sqrt_6N = sqrt(6*N)
    sqrt_6N_decimal = sqrt_6N % 1
    if sqrt_6N_decimal < 0.5:
        A = floor(sqrt_6N) + 0.5
    else:
        A = ceil(sqrt_6N)
    x = sqrt(A**2 - 6*N)
    # P = 3 * p
    # Q = 2 * q
    P = A - x
    p = mpz(P / 3)
    print(p)

def ex4():
    ciphertext = mpz(22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540)

    e = 65537

    p, q, N = ex1()
    fi_N = (p-1)*(q-1)

    d = invert(e, fi_N)

    plaintext = powmod(ciphertext, d, N)

    print(hex(plaintext))

ex1()
ex2()
ex3()
ex4()