Skip to content

Instantly share code, notes, and snippets.

@hierophantos
Created May 5, 2020 10:55
Show Gist options
  • Save hierophantos/2facf696ceeb9d59fe662e5cddd6d83c to your computer and use it in GitHub Desktop.
Save hierophantos/2facf696ceeb9d59fe662e5cddd6d83c to your computer and use it in GitHub Desktop.
%% schnorr grops
%% a basic sketch of zero-knowledge proofs [secret_sum/4]
%% 347, 173, 2
% (+P, +Q, -G)
schnorr_generator(P, Q, G) :-
R is (P - 1) / Q,
min_h(P, Q, H),
G is powm(H, R, P). %% G = H^R mod P
%% min_h(+P, +Q, -H)
min_h(P, Q, H) :-
prime_relation_check(P, Q),
R is (P - 1) / Q,
H #= 2, %% TODO: fix...
G is powm(H, R, P),
( G > 1
-> true
; NewH is H + 1,
min_h(P, R, NewH) %% this is broken H will never not be 2... which is usually correct
).
%% G^A * G^B (mod P) = G ^ ((A+B) mod Q) mod P
%% secret_sum(+P, +A, +B, -Proof)
%% @{eg} secret_sum(347, 23, 12, Proof), Proof = [_,_,Sum].
secret_sum(P, A, B, [GA, GB, Sum]) :-
safe_prime(P, Q),
schnorr_generator(P, Q, G),
X is (A + B) mod Q,
GA is powm(G, A, P), % for display purposes
GB is powm(G, B, P), % for display purposes
Sum is powm(G, X, P),
format("You have two numbers a and b whose sum is ~w (mod ~w).~n", [X, Q]),
format("Your proof is that ~w * ~w = ~w (mod ~w)", [GA, GB, Sum, P]).
generator_check(G, P, Q) :-
1 = powm(G, Q, P).
coprime(P, Q) :-
GCD is gcd(P, Q),
GCD = 1.
prime_relation_check(P, Q) :-
isPrime(P),
isPrime(Q),
1 #= P mod Q,
1 < (P - 1) / Q,
(P - 1) / Q < Q,
Q < P.
%% safe_prime(+P, -SP)
safe_prime(Prime, SafePrime) :-
isPrime(Prime),
SafePrime is ceiling((Prime - 1) / 2),
isPrime(SafePrime). %% do i need this last prime check?
%% primality check
isPrime(2) :- !.
isPrime(3) :- !.
isPrime(P) :-
P > 3,
P mod 2 =\= 0,
N_max is ceiling(sqrt(P)),
isPrime_(P, 3, N_max).
isPrime_(P, N, N_max) :-
( N > N_max
-> true
; 0 =\= P mod N,
M is N + 2,
isPrime_(P, M, N_max)
).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment