%
%  Simulazione di un round del protocollo d' 
        identificazione a conoscenza - zero di Fiat - Feige - 
      Shamir
%

Clear[p, q, n, v, b, s, r, x, y, z, vettoreBit, 
      vettoreBitSfida]

%  findBlum[t]
%  
          cerca primi congruenti a 3 mod 4 in una successione del tipo 4*k + 3;
%  t :  indice k da cui partire

%  dimVett :  dimensione dei vettori

dimVett = 16

findBlum[t_] := 
      Module[{n = 4*t + 3, k = t}, 
        While[Mod[n, 4] ≠ 3 || ! PrimeQ[n], k++; 
          n = 4*k + 3]; n]

p = findBlum[200]

%  verifica del numero trovato

PrimeQ[p]
Mod[p, 4]

q = findBlum[500]

n = p*q

%  calcola_v[b, s, n]
% restituisce il vettore di parametri pubblici dell' 
      identificando
%  b :  vettore di bit casuali
%  s :  
        vettore dei parametri segreti dell' 
          identificando
%  n :  il modulo

calcolaPubb[b_, s_, n_] := 
      Module[{i = 1, t = b}, 
        For[i = 1, i ≤ Length[s], i++, 
          t[[i]] = 
            Mod[Power[-1, b[[i]]]*PowerMod[s[[i]]^2, -1, n], 
              n]]; t]

vettoreBit = 
      Table[Random[Integer, {0, 1}], {dimVett}]
s = 
      Table[Random[
          Integer, {1, n - 1}], {Length[
            vettoreBit]}]
v = calcolaPubb[vettoreBit, s, n]

%  A prepara la testimonianza x

r = Random[Integer, {1, n - 1}]

b = Random[Integer, {0, 1}]

x = Mod[Power[-1, b]*r^2, n]

%  B prepara la sfida

vettoreBitSfida = 
      Table[Random[Integer, {0, 1}], {Length[s]}]

%  A risponde con y

y = 
      Mod[r*(∏_(i = 1)^(Length[s]))Power[s[[i]], 
              vettoreBitSfida[[i]]], n]

z = 
      Mod[(y^2)*(∏_(i = 1)^(Length[s]))Power[v[[i]], 
              vettoreBitSfida[[i]]], n]

% ...  e controlla che sia x congruente a  - 
      z oppure  + z :  
        in tal caso riconosce l' 
          identita' di A come autentica.

x

z

Mod[z + x, n]
Mod[z - x, n]

%  N . B .  : 
        z = 0 non dovrebbe essere accettato per prevenire il successo di un impostore che scelga r = 0