Ancillary material:
Below you find the source of some material featured in the text:
pseudo-code/source code of programs, figures, large numbers/string, etc.
For easy access, we list these sources by the page number in which they appear in the text.
0000001101 0001011111 1101011110 0111101000 0000101100 0100110100 0001110001
Miller-Rabin(BigInteger n, int s) { // returns ``true'' or ``false''
// tests whether n is prime;
// returns ``false'' if n is not prime;
// if it returns ``true'', then n is prime
// with probability at least 1 - 2 ** (-s).
BigInteger a;
for (int i = 1; i <= s; ++i) {
a = Random(2,n-1);
if Witness(a,n) return false;
}
return true;
}
Witness(BigInteger a, BigInteger n) {
// returns ``true'' if a is a witness for n not being prime;
// otherwise, it returns ``false'';
// the array b stores the binary representation of n - 1;
// and b[k] is the most significant bit,
// k being a global variable determined by n
int[] b;
BigInteger x;
BigInteger t = 1; // test value
for (int i = k; i >= 0; --i) {
x = t;
t = (t * t) mod n;
l1: if (t == 1 && x != 1 && x != n - 1) return true;
if (b[i] == 1) t = (t * a) mod n;
}
l2: if (t != 1) { return true; } else { return false; }
Witness(BigInteger a, BigInteger n) { // sliced
int[] b;
BigInteger t = 1; // test value
for (int i = k; i >= 0; --i) {
t = (t * t) mod n;
if (b[i] == 1) { t = (t * a) mod n; }
}
}
Euclid(BigInteger a, BigInteger b) {
if (b == 0) return a;
else return Euclid(b,a mod b);
}
number of bits trials
10 77
20 17
30 915
40 268
50 294
60 86
70 67
80 1355
90 254
100 569
110 543
120 886
130 405
140 80
150 51
160 776
170 1292
180 752
190 377
200 1 (how about that?;-)
... ...
512 1329
... ...
1024 1804
import java.io.*;
/** KeyboardReader implements keyboard input of strings, ints, and doubles. */
public class KeyboardReader
{ private BufferedReader k = new BufferedReader
(new InputStreamReader(System.in));
// the object built from System.in that reads a line of text
/** readString reads a string from the keyboard.
* @param message - the message that prompts the user for input
* @return the string the user types in response */
public String readString(String message)
{ System.out.print(message); System.out.flush();
try { return k.readLine(); }
catch (IOException e)
{ System.out.println("KeyboardReader input error"); return null; }
}
/** readInt reads an integer from the keyboard.
* @param message - the message that prompts the user for input
* @return the integer the user types in response */
public int readInt(String message)
{ return ( new Integer( readString(message) ).intValue() ); }
/** readDouble reads a double from the keyboard.
* @param message - the message that prompts the user for input
* @return the double the user types in response */
public double readDouble(String message)
{ return ( new Double( readString(message) ).doubleValue() ); }
}
import java.math.*;
import java.util.*;
public class Prime_Count {
private static KeyboardReader keyboard = new KeyboardReader();
public static void main(String[] args) {
Random seed;
BigInteger p;
int l = keyboard.readInt("number of bits of prime: ");
int counter = 0;
do {
seed = new Random();
p = new BigInteger(l, seed);
counter++;
} while (!p.isProbablePrime(50));
System.out.println(counter + " trials to find prime " + p);
}
}
Extended_Euclid(BigInteger x, BigInteger y) {
BigInteger d, d', r, r', s, s';
if (y == 0) return (x,1,0);
else {
(d',r',s') = Extended_Euclid(y,x mod y);
(d,r,s) = (d',s',r' - floorint(x/y) * s');
return (d,r,s);
}
}
Linear(BigInteger a, BigInteger b, BigInteger n) {
BigInteger d, x', y', x0;
if (b mod d == 0) {
x0 = x' * (b / d) mod n;
for (int i = 0; i <= d-1; ++i) {
printout x0 + i * (n / d) mod n;
} else
printout ``no solutions'';
}
Pollard-Rho(BigInteger n) {
// tries to compute a non-trivial factor of n
// by placing a random seed x with 2 <= x <= n - 1
// and then running a deterministic algorithm with
// x and n as parameters
int i = 1;
BigInteger d;
BigInteger x = Random(2, n - 1);
BigInteger y = x;
int k = 2;
while true {
++i;
x = (x * x - 1) mod n;
d = gcD(y - x, n);
if (d != 1 && d != n) { printout ``one factor is: '' d;
stop;
}
else {
if (k = i) { y = x;
k = 2 * k;}
}
}
}
0111000000 1101001111 0001001100 1110001010 0100000000 1011010000 1101101101
1000110011 0010010001 0111111111 1100101110 1100001001 1010110110 1000101000
1001110001 1110100000 1101001010 0100011011 0101110001 0001110000 1111000100
1110111000 0001001100 1011010110 0001001010 1111001001 1010101000 0001001001
1001000111 1010010100 1000101111 0011101010 1011101001 0000100010 0101010010
0010110100 1011110001 0010100101 1000111101 1100001100 11111010011 100110010;
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
C0
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
D_0
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
round number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# of left shifts 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
x/y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S_2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S_3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S_4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S_5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S_6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S_7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S_8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
RijndaelEncryption(State, CipherKey) {
KeyExpansion(CipherKey, ExpandedKey);
AddRoundKey(State, ExpandedKey);
for ( i = 1; i < Nr; i++ ) { Round(State,ExpandedKey[Nb*i]); }
FinalRound(State, ExpandedKey[Nb*Nr]);
}
Round(State, Roundkey) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State, RoundKey);
}
FinalRound(State, RoundKey) {
ByteSub(State);
ShiftRow(State);
AddRoundKey(State, RoundKey);
}
KeyExpansion(byte[] Key, word[] Exp) {
// input: an 8bit byte array Key with index range 0..4*Nk-1
// output: a 32bit word array Exp with index range 0..Nb*(Nr+1)-1
// precondition: Nk <= 6
for ( i = 0; i < Nk; i++ ) {
Exp[i] = (Key[4*i], Key[4*i+1], Key[4*i+2], Key[4*i+3]);
}
for ( i = Nk; i < Nb*(Nr+1); i++ ) {
temp = Exp[i-1];
if (i % Nk == 0) { temp = SubByte(RotByte(temp)) XOR Rcon[i/Nk]; }
Exp[i] = Exp[i-Nk] XOR temp;
}
}
KeyExpansion(byte[] Key, word[] Exp) {
// input: an 8bit byte array Key with index range 0..4*Nk-1
// output: a 32bit word array Exp with index range 0..Nb*(Nr+1)-1
// precondition: Nk = 8
for ( i = 0; i < Nk; i++ ) {
Exp[i] = (Key[4*i], Key[4*i+1], Key[4*i+2], Key[4*i+3]);
}
for ( i = Nk; i < Nb*(Nr+1); i++ ) {
temp = Exp[i-1];
if (i % Nk == 0) { temp = SubByte(RotByte(temp)) XOR Rcon[i/Nk];
} else { if (i % Nk = 4) { temp = SubByte(temp); }
}
Exp[i] = Exp[i-Nk] XOR temp;
}
}
InvRound(State, RoundKey) {
AddRoundKey(State, RoundKey); // is its own inverse
InvMixColumn(State); // like MixColumn but based on d(x)
InvShiftRow(State); // like ShiftRow but with Nb-Ci
InvByteSub(State); // 1st: undo affine map; 2nd: inverse
}
InvFinalRound(State, Roundkey) {
AddRoundKey(State, RoundKey);
InvShiftRow(State);
InvByteSub(State);
}
RijndaelDecryption(State, CipherKey) {
InvKeyExpansion(CipherKey, InvExpandedKey);
AddRoundKey(State, InvExpandedKey[Nb*Nr]);
for ( i = Nr - 1; i > 0; i-- ) {
Round(State,InvExpandedKey[Nb*i]);
}
FinalRound(State, InvExpandedKey[0]);
}
InvRound(State, InvRoundKey) {
InvByteSub(State);
InvShiftRow(State);
InvMixColumn(State);
AddRoundKey(State, InvRoundKey);
}
InvFinalRound(State, InvRoundKey) {
InvByteSub(State);
InvShiftRow(State);
AddRoundKey(State, InvRoundKey);
}
Secure_Hash_Standard(Block[] M, int n) {
// input: a non-empty array of 512bit blocks
// M[0], M[1], ..., M[n-1] such that 512 * n < 2**64
// output: a 160bit hash value represented by the concatenation
// H0H1H2H3H4 of the final values of the five 32bit words H0 to H4
// the pseudo-code assumes the functions f[t] and constants K[t] for
// 0 <= t <= 79 as defined in the text above
// initialization of each Hi as a sequence of eight hex digits
Word H0 = 67452301;
Word H1 = EFCDAB89;
Word H2 = 98BADCFE;
Word H3 = 10325476;
Word H4 = C3D2E1F0;
Word A,B,C,D,E;
Word TEMP;
// an array which holds eighty words W[0], ..., W[79]
Word[] = W;
for (int i = 0; i < n; ++i) {
assign to W[0] the left-most 32 bits of M[i];
assign to W[1] the next 32 left-most bits of M[i];
...
assign to W[15] the 32 right-most bits of M[i];
// at this point, the concatenation W[0]W[1]...W[15] equals M[i]
for (int j = 16; j < 80; ++j) {
// Shift(n,W) computes a circular shift of W by n positions to the left
W[j] = Shift(1,W[j-3] XOR W[j-8] XOR W[j-14] XOR W[j-16]);
}
A = H0; B = H1; C = H2; D = H3; E = H4;
for (int t = 0; t < 80; ++t) {
// + is the operation on words as defined in the text above
TEMP = Shift(5,A) + f[t](B,C,D) + E + W[t] + K[t];
E = D; D = C; C = Shift(30,B); B = A; A = TEMP;
}
H0 = H0 + A;
H1 = H1 + B;
H2 = H2 + C;
H3 = H3 + D;
H4 = H4 + E;
}
return the concatenation H0H1H2H3H4;
}
Alternate_Secure_Hash_Standard(Block[] M, int n) {
// requires only W[0] to W[15] and a mask Mask
// instead of the entire array W[0] to W[79]
...
// the initial part up to the for-statement below is as before
Word Mask = 0000000F; // implements ``W[0] == W[16]''
for (int i = 0; i < n; ++i) {
compute W[0] to W[15] as before;
A = H0; B = H1; C = H2; D = H3; E = H4; // as before
int s;
for (int t = 0; t < 80; ++t) {
// in the next two statements, we identify integers with 32bit words
s = t AND MASK;
if (t >= 16) {
W[s] = Shift(1,W[(s+13) AND Mask] XOR W[(s+8) AND Mask] XOR
W[(s+2) AND Mask] XOR W[s]);
}
TEMP = Shift(5,A) + f[t](B,C,D) + E + W[s] + K[t];
// W[t] from previous version changes to W[s]
E = D; D = C; C = Shift(30,B); B = A; A = TEMP; // as before
}
... // as before
}
3A8CD51B 01A4C7B2 378C251B 01A8C7C2
3ABC251B 01A4C7B2 3A8CE51B 01C4C7F2
3A8C171B 0194C5B2 3A8C241B 01A4C762
0A8C251B 01A4C7B2
DSS_Prime_Generation(int l,int lseed) {
// generates two prime numbers p and q for the DSS
// input: * an integer l between 0 and 8
// * an integer lseed, the length of the seed
// output: * a 160bit prime q and a prime p with 512 + 64*l bits
// such that q divides p - 1
// * the value of an internal counter
// * the value of the successful seed
int L = 512 + 64 * l;
int n = L - 1 div 160;
int b = L - 1 mod 160;
bool q_not_prime = true;
loc: while q_not_Prime {
BigInteger seed = Random(1,2**lseed - 1) XOR 2**(lseed - 1);
BigInteger u = hash(seed) XOR hash(seed + 1\mod 2**lseed);
BigInteger q = u OR 2**159 OR 1;
q_not_prime = Miller-Rabin(q,80);
}
int counter = 0;
int offset = 2;
while counter <= 4096 {
for (int k = 0; k <= n; ++k) {
v[k] = hash(seed + offset + k mod 2**lseed);
}
BigInteger w = v[0];
for (int k = 1; k < n; ++k) { w = w + v[k] * 2**(k*160); }
w = w + (v[n] mod 2**b) * 2**(2*160);
BigInteger x = w + 2**(L - 1);
BigInteger c = x mod 2*q;
BigInteger p = x - (c - 1);
if (p >= 2**(L-1) && Miller-Rabin(p,80)) {
return (q,p,counter,seed);
}
counter = counter + 1;
offset = offset + n + 1;
}
goto loc;
}
randomly generated prime p: 342853815608923
evaluation point v[0]: 111350135012507
evaluation point v[1]: 207244959855905
evaluation point v[2]: 20545949133543
coefficient a[1]: 53958111706386
coefficient a[2]: 151595058245452
secret s: 151595058245452
share f(v[0]): 109351520587519
share f(v[1]): 174675701531216
share f(v[2]): 117471713218253
weight b[0]: 266921901220910
weight b[1]: 129147516050688
weight b[2]: 289638213946249
recovered secret: 151595058245452
prime p: 386635119272011
evaluation point v[0]: 289606484363304
evaluation point v[1]: 228145533986232
evaluation point v[2]: 330844624449199
share value f(v[0]): 249291108939758
share value f(v[1]): 197249960673620
share value f(v[2]): 250460653862862
main(Protocol p) {
s := initial global state of p;
return found_a_bug?(s);
}
found_a_bug?(GlobalState s) {
while (nextstate_of s) {
for all agents A and B {
if (C_i(A,B) < 0 || C_r(A,B) < 0) return true;
}
for all m in S_temp or m in S_safe {
if m in I_Z return true;
}
return disjunction of all found_a_bug?(s'),
s' any next state of s
}
function member?(m,B) {
*/ m ::= a | m1 * m2 | E_k(m) | D_k(m) */
*/ B is a finite, non-redundant set of messages to which */
*/ no elimination rules apply */
if ((m == a) | (m == D_k(m'))) { return element_of(m,B);
} elseif (m == m1 * m2) { return (member?(m1,B) && member?(m2,B));
} elseif (m == E_k(m')) { return (member?(E_k,B) && member?(m',B));
} else { raise exception;}
}
function update(m,B) {
*/ m ::= a | m1 * m2 | E_k(m) | D_k(m) */
*/ B is a finite, non-redundant set of messages to which */
*/ no elimination rules apply */
if member?(m,B) { return B; }
if (m == D_k) { // check whether B contains a matching cipher-text
L := B;
n := head(L);
while (L != []) {
if (n == E_k(m') {
return update(m',B); // ... if so, update accordingly
}
L := tail(L);
n := head(L);
}
}
// at this point, a is not a member of B
if (m == a) { return (m :: B); }
if (m == m1 * m2) { return update(m2,update(m1,B)); }
if (m = E_k(m') && element_of(D_k,B)) {
// know key for cipher-text
if (element_of(E_k,B)) {
return update(m',B);
// no need to store m, storing m' suffices
} else { return update(m',m :: B); } // need m and possibly m'
}
return m :: B; // at this point, m is not implicitly known
}
1. A --> B : A.B.{n_a.A }E_B
2. B --> A : B.A.{n_a.n_b}E_A
3. A --> B : A.B.{n_b}E_B
1. A --> B : A.B.{n_a.A }E_B
2. B --> A : B.A.{n_a.n_b.B}E_A
3. A --> B : A.B.{n_b}E_B
1. A --> B : A
2. B --> A : n_b
3. A --> B : {n_b}k_as
4. B --> S : {A.{n_b}k_as}k_bs
5. S --> B : {A.n_b}k_bs
function Plain_text_aware_encryption(bitstring message,
bitstring random_coins) {
// encrypts message of less than k - 319 bits with RSA function f
// in a plain-text-aware manner
// zeros: a bit string of zeros of
// bit length k - 192 - length_of(message)
// input: * a bit string, message, of bit length less than k - 319
// * a bit string, random_coins, of arbitrary length
// output: * the k bit encryption of message with function f
sigma = hash_str(desc);
// desc is the string describing function f
sigma1 = hash_sigma(<1>);
// <1> is the 32bit binary of the number 1
sigma2 = hash_sigma(<2>);
sigma3 = hash_sigma(<3>);
i = 0;
do {
r = HASH(sigma1, 128, || random_coins);
// || is concatenation
x = key_data || < length_of(message) > || zeros || message;
x1 = x XOR HASH(sigma2, length_of(x), r);
r1 = r XOR HASH(sigma3, 128, x1);
r_x = x1 || r1;
++i;
} while (!inMessageSpace(r_x));
return f(r_x);
}
RSA_encryption(BigInteger m, BigInteger n) {
// returns m ** d mod n, where d is the secret RSA key and
// n is the RSA modulus
// the array b stores the binary representation of d
// and has been ``entered'' into the program via a
// ``secure'' mechanism;
// b[k] is the most significant bit of d
int[] b;
BigInteger c = 1; // identifier for cipher-text
for (int i = k; i >= 0; --i) {
c = (c * c) mod n;
if (b[i] == 1) c = (c * m) mod n;
}
return c;
}