strawmelonjuice.com
Forking what is left of ZeroNet and hopefully adding an AT Proto Frontend/Proxy
1def int_to_bytes(raw, length):
2 data = []
3 for _ in range(length):
4 data.append(raw % 256)
5 raw //= 256
6 return bytes(data[::-1])
7
8
9def bytes_to_int(data):
10 raw = 0
11 for byte in data:
12 raw = raw * 256 + byte
13 return raw
14
15
16def legendre(a, p):
17 res = pow(a, (p - 1) // 2, p)
18 if res == p - 1:
19 return -1
20 else:
21 return res
22
23
24def inverse(a, n):
25 if a == 0:
26 return 0
27 lm, hm = 1, 0
28 low, high = a % n, n
29 while low > 1:
30 r = high // low
31 nm, new = hm - lm * r, high - low * r
32 lm, low, hm, high = nm, new, lm, low
33 return lm % n
34
35
36def square_root_mod_prime(n, p):
37 if n == 0:
38 return 0
39 if p == 2:
40 return n # We should never get here but it might be useful
41 if legendre(n, p) != 1:
42 raise ValueError("No square root")
43 # Optimizations
44 if p % 4 == 3:
45 return pow(n, (p + 1) // 4, p)
46 # 1. By factoring out powers of 2, find Q and S such that p - 1 =
47 # Q * 2 ** S with Q odd
48 q = p - 1
49 s = 0
50 while q % 2 == 0:
51 q //= 2
52 s += 1
53 # 2. Search for z in Z/pZ which is a quadratic non-residue
54 z = 1
55 while legendre(z, p) != -1:
56 z += 1
57 m, c, t, r = s, pow(z, q, p), pow(n, q, p), pow(n, (q + 1) // 2, p)
58 while True:
59 if t == 0:
60 return 0
61 elif t == 1:
62 return r
63 # Use repeated squaring to find the least i, 0 < i < M, such
64 # that t ** (2 ** i) = 1
65 t_sq = t
66 i = 0
67 for i in range(1, m):
68 t_sq = t_sq * t_sq % p
69 if t_sq == 1:
70 break
71 else:
72 raise ValueError("Should never get here")
73 # Let b = c ** (2 ** (m - i - 1))
74 b = pow(c, 2 ** (m - i - 1), p)
75 m = i
76 c = b * b % p
77 t = t * b * b % p
78 r = r * b % p
79 return r