modular-shenanigans/main.py at master · Luminic/modular-shenanigans · 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
def mul(a,b,m):
    if b<a:
        a,b=b,a
    r=0
    while a>0:
        if a&1:
            r=(r+b)%m
        a>>=1
        b=(b<<1)%m
    return r

def pow(a,b,m):
    b%=m-1
    p=1
    while b!=0:
        if b%2==1:
            p=mul(p,a,m)
        b>>=1
        a=mul(a,a,m)
    return p

def div(a,b,m):
    return mul(a,minv(b,m),m)

def minv(a,m):
    b=m
    c,d=0,1
    while a!=1:
        # extended euclidian algorithm
        c,d=d,(c-mul(d,b//a,m))%m
        # euclidian algorithm
        b,a=a,b%a
    return d


import math

def add(A,B,a,b,m):
    ax,ay=A
    bx,by=B
    if math.isinf(ay):
        return B
    if math.isinf(by):
        return A
    if A==B:
        return double(A,a,b,m)
    if ax==bx:
        return (0,math.inf)
    s=div((by-ay)%m,(bx-ax)%m,m)
    x=(mul(s,s,m)-ax-bx)%m
    y=(mul(s,(ax-x)%m,m)-ay)%m
    return (x,y)

def double(A,a,b,m):
    ax,ay=A
    if math.isinf(ay):
        return A
    if ay==0:
        return (0,math.inf)
    s=div((3*mul(ax,ax,m)+a)%m,(2*ay)%m,m)
    x=(mul(s,s,m)-2*ax)%m
    y=(mul(s,(ax-x)%m,m)-ay)%m
    return (x,y)

def scalar(A,k,a,b,m):
    R=(0,math.inf)
    while k>0:
        if k&1:
            R=add(R,A,a,b,m)
        k>>=1
        A=double(A,a,b,m)
    return R

def verify(A,a,b,m):
    ax,ay=A
    return math.isinf(ay) or mul(ay,ay,m)==(mul(mul(ax,ax,m),ax,m)+mul(a,ax,m)+b)%m

import random

def find_secret_key(G,Key1,Key2,a,b,m):
    A=G
    c=1
    while Key1!=A and Key2!=A:
        A=add(A,G,a,b,m)
        c+=1
    if Key1==A:
        return scalar(Key2,c,a,b,m)
    else:
        return scalar(Key1,c,a,b,m)

def find_valid(a,b,m):
    if m%4==3:
        while True:
            x=random.randint(0,m)
            ex=(pow(x,3,m)+mul(a,x,m)+b)%m
            if 1==pow(ex,m//2,m):
                y=pow(ex,(m+1)//4,m)
                if verify((x,y),a,b,m):
                    return (x,y)

def main():
    a,b=124819,1234512
    p=10000019
    G=find_valid(a,b,p)
    print("Generator")
    print(G)
    print("Transmitted data")
    secret_key=random.randint(0,p)
    my_key=random.randint(0,p)
    what_you_send_me=scalar(G,secret_key,a,b,p)
    print(what_you_send_me)
    what_i_send_you=scalar(G,my_key,a,b,p)
    print(what_i_send_you)
    your_shared_key=scalar(what_i_send_you,secret_key,a,b,p)
    my_shared_key=scalar(what_you_send_me,my_key,a,b,p)
    print("Secret from onlookers")
    print(your_shared_key)
    print(my_shared_key)
    print("Brute force attack")
    print(find_secret_key(G,what_i_send_you,what_you_send_me,a,b,p))

main()