-
Notifications
You must be signed in to change notification settings - Fork 0
/
Schnorr.sage
131 lines (100 loc) · 2.85 KB
/
Schnorr.sage
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
124
125
126
127
128
from sage.cpython.string import str_to_bytes
import hashlib
import math
def hashN(x0, x1):
return N(int(hashlib.sha256(x0+x1).hexdigest(),16))
def countBits(number):
return int((math.log(number) /
math.log(2)));
F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
C = EllipticCurve ([F (0), F (7)])
#y^2 = x^3 + ax + b standard curve
#y^2 = x^3 + 0*x + 7 this curve
G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
lambdaParameter = countBits(C.order())
N = FiniteField (C.order())
print(G.order())
K = []
PX = N.random_element()
X = int(PX) * G
def padbytes(byteslist):
if len(byteslist) >= 64:
return byteslist
else:
return padbytes(b'0' + byteslist)
def encode(R):
xy = R.xy()
x = int(xy[0])
y = int(xy[1])
result = b''
if y % 2:
result += b'3'
else:
result += b'2'
result += padbytes(bytes(hex(x), "utf8")[2:])
return result
def sign1(i, c):
return
R = []
M = []
C = []
S = []
CB = []
zero = []
#Generate zero array
for i in range(0, lambdaParameter):
zero.append(N(0))
for i in range(0, lambdaParameter):
#Generate nonse
k = N.random_element()
K.append(k)
#Generate public version of nonse
r = int(k) * G
R.append(r)
#Generate two messages in which we will ask the server to sign
m0 = bytes(str(int(N.random_element())), "utf8")
m1 = bytes(str(int(N.random_element())), "utf8")
#Hash our public nonse with the message as the aux string
c0 = hashN(encode(r), m0)
c1 = hashN(encode(r), m1)
M.append([m0[:], m1[:]])
C.append([c0, c1])
#Run the P256 function with the zero vector to get the 256th term of the hashes
p256256 = 0
for i in range(0, len(zero)):
a = zero[i] - C[i][0]
b = C[i][1] - C[i][0]
p256256 += (N(2^i) / b) * a
#Run the P256 function with the public nonses to get a public nonse with the 256 term added on after multiplyied by the public key
r256 = 0
for i in range(0, len(R)):
a = R[i] - int(C[i][0]) * G
b = C[i][1] - C[i][0]
r256 += int(N(2^i) / b) * a
r256 += (int(p256256) * X)
#Generate the message we wish to forge a signature for
m256 = N.random_element()
#Hash the new public nonse and messagee
c256 = hashN(encode(r256), bytes(str(int(m256)), "utf8"))
#Turn the hash into a binary string
b = f'{int(c256):0256b}'
B = []
for i in range(1, lambdaParameter+1):
B.append(b[i-1:i])
B.reverse()
#Choose the correct message hashes by the binary string generated
for i in range(0, lambdaParameter):
CB.append(C[i][int(B[i], 2)])
#Ask the server for the signatures for the correct hashes
for i in range(0, lambdaParameter):
si = K[i] - N(PX) * N(CB[i])
S.append(si)
#Run the P256 function with the signatures to get the final signature
s256 = 0
for i in range(0, len(S)):
a = S[i] - C[i][0]
b = C[i][1] - C[i][0]
s256 += (N(2^i) / b) * a
S.append(s256)
#Verify the final signature
print(((int(s256) * G) + (int(c256) * X)) == r256)