|
#Encrypt: encrypted_hash = encrypt(passwd) |
|
#Check is correct passwd: is_correct = check_passwd(passwd, encrypted_has) |
|
#Example API: type ./encrypt.py to see usage |
|
|
|
def legendre(a, m): |
|
return pow(a, (m-1) >> 1, m) |
|
|
|
# strong probable prime |
|
def is_sprp(n, b=2): |
|
d = n-1 |
|
s = 0 |
|
while d&1 == 0: |
|
s += 1 |
|
d >>= 1 |
|
|
|
x = pow(b, d, n) |
|
if x == 1 or x == n-1: |
|
return True |
|
|
|
for r in range(1, s): |
|
x = (x * x)%n |
|
if x == 1: |
|
return False |
|
elif x == n-1: |
|
return True |
|
|
|
return False |
|
|
|
# lucas probable prime |
|
# assumes D = 1 (mod 4), (D|n) = -1 |
|
def is_lucas_prp(n, D): |
|
Q = (1-D) >> 2 |
|
|
|
# n+1 = 2**r*s where s is odd |
|
s = n+1 |
|
r = 0 |
|
while s&1 == 0: |
|
r += 1 |
|
s >>= 1 |
|
|
|
# calculate the bit reversal of (odd) s |
|
# e.g. 19 (10011) <=> 25 (11001) |
|
t = 0 |
|
while s > 0: |
|
if s&1: |
|
t += 1 |
|
s -= 1 |
|
else: |
|
t <<= 1 |
|
s >>= 1 |
|
|
|
# use the same bit reversal process to calculate the sth Lucas number |
|
# keep track of q = Q**n as we go |
|
U = 0 |
|
V = 2 |
|
q = 1 |
|
# mod_inv(2, n) |
|
inv_2 = (n+1) >> 1 |
|
while t > 0: |
|
if t&1 == 1: |
|
# U, V of n+1 |
|
U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n |
|
q = (q * Q)%n |
|
t -= 1 |
|
else: |
|
# U, V of n*2 |
|
U, V = (U * V)%n, (V * V - 2 * q)%n |
|
q = (q * q)%n |
|
t >>= 1 |
|
|
|
# double s until we have the 2**r*sth Lucas number |
|
while r > 0: |
|
U, V = (U * V)%n, (V * V - 2 * q)%n |
|
q = (q * q)%n |
|
r -= 1 |
|
|
|
# primality check |
|
# if n is prime, n divides the n+1st Lucas number, given the assumptions |
|
return U == 0 |
|
|
|
# primes less than 212 |
|
small_primes = set([ |
|
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, |
|
31, 37, 41, 43, 47, 53, 59, 61, 67, 71, |
|
73, 79, 83, 89, 97,101,103,107,109,113, |
|
127,131,137,139,149,151,157,163,167,173, |
|
179,181,191,193,197,199,211]) |
|
|
|
# pre-calced sieve of eratosthenes for n = 2, 3, 5, 7 |
|
indices = [ |
|
1, 11, 13, 17, 19, 23, 29, 31, 37, 41, |
|
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, |
|
89, 97,101,103,107,109,113,121,127,131, |
|
137,139,143,149,151,157,163,167,169,173, |
|
179,181,187,191,193,197,199,209] |
|
|
|
# distances between sieve values |
|
offsets = [ |
|
10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, |
|
6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, |
|
2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, |
|
4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2] |
|
|
|
max_int = 2147483647 |
|
|
|
# an 'almost certain' primality check |
|
def is_prime(n): |
|
if n < 212: |
|
return n in small_primes |
|
|
|
for p in small_primes: |
|
if n%p == 0: |
|
return False |
|
|
|
# if n is a 32-bit integer, perform full trial division |
|
if n <= max_int: |
|
i = 211 |
|
while i*i < n: |
|
for o in offsets: |
|
i += o |
|
if n%i == 0: |
|
return False |
|
return True |
|
|
|
# Baillie-PSW |
|
# this is technically a probabalistic test, but there are no known pseudoprimes |
|
if not is_sprp(n): return False |
|
a = 5 |
|
s = 2 |
|
while legendre(a, n) != n-1: |
|
s = -s |
|
a = s-a |
|
return is_lucas_prp(n, a) |
|
|
|
# next prime strictly larger than n |
|
def next_prime(n): |
|
if n < 2: |
|
return 2 |
|
# first odd larger than n |
|
n = (n + 1) | 1 |
|
if n < 212: |
|
while True: |
|
if n in small_primes: |
|
return n |
|
n += 2 |
|
|
|
# find our position in the sieve rotation via binary search |
|
x = int(n%210) |
|
s = 0 |
|
e = 47 |
|
m = 24 |
|
while m != e: |
|
if indices[m] < x: |
|
s = m |
|
m = (s + e + 1) >> 1 |
|
else: |
|
e = m |
|
m = (s + e) >> 1 |
|
|
|
i = int(n + (indices[m] - x)) |
|
# adjust offsets |
|
offs = offsets[m:]+offsets[:m] |
|
while True: |
|
for o in offs: |
|
if is_prime(i): |
|
return i |
|
i += o |
|
#from time import clock |
|
import hashlib |
|
from random import random |
|
|
|
def encrypt(s): |
|
n = 0 |
|
for byte in bytearray(hashlib.sha512(s.encode('utf-8')).digest()): |
|
n = n<<8 | byte |
|
m = next_prime(n) |
|
n = 0 |
|
for byte in bytearray(hashlib.sha512(str(random()).encode('utf-8')).digest()): |
|
n = n<<8 | byte |
|
q = next_prime(n) |
|
return "%x"%(m*q) |
|
|
|
def check_passwd(passwd, public): |
|
n = int(public, 16) |
|
p = 0 |
|
for byte in bytearray(hashlib.sha512(passwd.encode('utf-8')).digest()): |
|
p = p<<8 | byte |
|
p = next_prime(p) |
|
return n%p==0 |
|
|
|
def main(): |
|
import sys |
|
from getpass import getpass |
|
def exit_with_help(): |
|
print('Usage: %s {e,c} [pub]') |
|
print('e: encrypt given code (from keyboard or pipe)') |
|
print('c: check given code match the pub file') |
|
sys.exit(1) |
|
argv = sys.argv |
|
if len(argv) < 2: |
|
exit_with_help() |
|
opt = argv[1] |
|
if opt == 'e': |
|
if sys.stdin.isatty(): |
|
code = getpass('code: ') |
|
else: |
|
code = sys.stdin.readline().rstrip() |
|
print(encrypt(code)) |
|
elif opt == 'c': |
|
with open(argv[2]) as pub_f: |
|
pub = '\n'.join(pub_f.readlines()).strip() |
|
if sys.stdin.isatty(): |
|
code = getpass('code: ') |
|
else: |
|
code = sys.stdin.readline().rstrip() |
|
print('True' if check_passwd(code, pub) else 'False') |
|
else: |
|
exit_with_help() |
|
|
|
|
|
if __name__ == '__main__': |
|
main() |