schnorr_groups.pl

%% 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)
    ).