Number Theory for Computing

378 3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Secu 379 is 3 .3 .8 Elliptic Curve Public-Key Cryptosystem s [3-1] Evaluates the Legendre We have discussed some novel applications of elliptic curves in primality test- ing and integer factorization in Chapter 2 . In this subsection . we shall intro- . duce one more novel application of elliptic curves in public Key cryptography . =(3)—(3)—1 More specifically. we shall introduce elliptic curve analogues of several well- known public key ct y ptosystems . including the Diffie- Hellman key exchang e = ( 5) = ( 2 = —l. system and the RSA cryptos}stem . 33 (I) Brief History of Elliptic Curve Cryptography . Elliptic curves hav e been extensively studied by number theorists for more than one hundre d c, years, only for their mathematical beauty, not for their applications . However , [3-2] Evaluates the Legends symbols in the late 1980s and early 1990s many important applications of ellipti c curves in both mathematics and computer science were discovered, notably 4 applications of ellipticcurves in primality testing (see Kilian [120] and Atki n and Morain [12]) and integer factorization (see Lenstra [1 .40]), both discusse d 4) = in Chapter 2 . Applications of elliptic curves in cryptography were not found (16) until the following two seminal papers were published : C cq ~ = ( - ) =-1 . (1) Victor Miller, \"Uses of Elliptic Curves in Cryptography\" , 1986 . (See [3-3] Further by Equation (3 .88) . Alice get s [163] . ) rn 2 = 0, since = e '.; = 1 . (2) Neal Koblitz°, \"Elliptic Curve Cryptosystems\" . 1987 . (See [126] . ) m 3 = 1, since 63 = _ -1 . Since then, elliptic curves have been studied extensively for the purpose o f Remark 3 .3 .8 . The scheme introduced above is a good extension of th e cryptography, and many practically more secure encryption and digital sig- public-key idea, but encrypts messages bit by bit . It is completely secur e nature schemes have been developed based on elliptic curves . Now ellipti c with respect to semantic security as well as bit security'' . However . a majo r curve cryptography (ECC) is a standard term in the field and there is a text - disadvantage of the scheme is the message expansion by a factor of log n bit . book by Menezes [155] that is solely devoted to elliptic curve cryptography . To improve the efficiency of the schem e ; Blum and Goldwasser [28] propose d There is even a computer company in Canada, called Certicom . which is a another randomized encryption scheme . in which the ciphertext is only longe r leading provider of cryptographic technology based on elliptic curves . In the than the plainext by a constant number of bits : this scheme is comparable t o subsections that follow, we shall discuss the basic ideas and computationa l the RSA scheme . both in terms of speed and message expansion . methods of elliptic curve cryptography. Exercise 3 .3 .8 . RSA encryption scheme is deterministic and not semanti- Neal Noblitz received his BSc degree in mathematics from Harvar d cally secure, but it can be made semantically secure by adding randomness t o University in 1969 . and his PhD in arithmetic algebraic geometr y the encryption process (Bellare and Rogayyay . [22]) . Develop an RSA base d from Princeton in 1974 . From 1979 to the present, he has been a t probabilistic (randomized) encryption scheme that is semantically secure . the University of Washington in Seattle . where he is now a pro- fessor in mathematics . In recent years ins research interests hav e Several other cryptographic schemes . including digital signature scheme s been centered around the applications of number theory- in cryp - and authentication encryption schemes are based on the quadratic residuosit y tography=. He has published a. couple of books in related to number problem (QRP) : interested readers are referred to . for example, Chen [47] an d theory and cryptography. two of there are as follows : A Cours e Nrang [175] for some recent developments and applications of the quadrati c in \\umber Theory and Cryptography [128], and Algebraic Aspects of Cryptogra- phv [129] . His other interests include pre university math education . mathematical residuosity based cryptosystems . development in the Third World, and snorkeling . (Photo by courtesy of Springer- Verlag . ) '' Bit. security is a special case of semantic security- . Informally. bit security i s concerned with not only that the whole message is not recoverable but also tha t individual bits of the message are not recoverable . The main drawback of th e scheme is that the encrypted message is much longer than its original plaintext .

3 . Appl i ed Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 38 1 380 (II) Precomputations of Elliptic Curve Cryptography . To implemen t If we happen to know N, the number of points on our elliptic curve E elliptic curve cryptography, we need to do the following precomputations : and if k > N, then the coordinates of AT on E can he computed i n [1] Embed Messages on Elliptic Curves : Our aim here is to do cryptography with elliptic curve groups in place of F q . More specifically, we wish to 0(log q) 1 bit operations [128] : recall that the number ~T of points on E embed plaintext messages as points on an elliptic curve defined over a satisfies N < q+ 1+ 214 = 0(q) and can be computed by Rene Schoof s finite field Fq , with q = p r and p E Primes . Let our message units m b e integers 0 < m < M . let also K be a large enough integer for us to b e algorithm in 0(logq) 8 bit operations . satisfied with an error probability of 2 – ^ when we attempt to embed a [3] Compute Discrete Logarithms on Elliptic Curves : Let E be an elliptic plaintext message in . In practice, 30 < k, < 50 . Now let us take K = 3 0 and an elliptic curve E : ,y '- = :r 3 + ax + b over Fq . Given a message curve over Fq . and B a point on E . Then the discrete logarithm on E is the number rn, we compute a set of values for x : problem : given a point P E E . find an integer x E 7L such that .rB = P i f {mK + j, j = O . 1 .2 . - } = {30m .. 30m + 1, 30m + 2, . . . } (3 .89 ) such an integer x exists . It is likely that the discrete logarithm proble m on elliptic curves over Fq is more intractable than the discrete logarith m until we find 1;-3 + ax + b is a square modulo p . giving us a . poin t (x . 3x3 + ax + b) on E . To convert a point (x . y) on E hack to a mes- problem in Fq . It is this feature that makes cryptographic systems based sage number m, we just compute m = [x/30J . Since x 3 + ax + b is a square for approximately 50% of all x . there is only about a. 2 – \" prob- on elliptic curves even more secure than that based on the discrete log- ability that this method will fail to produce a point on E over Fq . I n what follows, we shall give a simple example of how to embed a . mes- arithm problem . In the rest of this subsection, we shall discuss ellipti c sage number by a point on an elliptic curve . Let E be y 2 = x3 + 3x , curve analogues for some of the important public key cryptosystems . nr = 2174 and p = 4177 (in practice, we select p > 30m,) . Then we calcu - late x = {30 . 2174 + j . j = 0, 1, 2, . . . } until x 3  3x is a square modul o (III) Elliptic Curve Analogues of Some Public-Key Cryptosystems . 4177 . We find that when j = 15 : In what follows . we shall introduce elliptic curve analogues of four widely used public-key cryptosystems, namely the Diffie–Hellman key exchange system . x = 302174+1 5 the Massey Omura, the ElGamal and the RSA public-key cryptosystems . = 6523 5 (1) Analogue of the Difie–Hellman Key Exchange System : x 3 +3x = (30 . 2174+15) 3 +3(302174+ 15 ) [1]Alice and Bob publicly choose a finite field F q with q = pr and p E Primes . = 27761440704858 0 an elliptic curve E over Fq . and a random base point P E E such that P generates a large subgroup of E, preferably of the same size as that of E 1444 mod 417 7 itself . 38 2 [2] To agree on a secret key, Alice and Bob choose two secret random integer s So we get the message point for rn = 2174 : a and b . Alice computes aP E E and sends aP to Bob : Bob compute s bP E E and sends bP to Alice . Both aP and bP are . of course, public (x. V.r 3 + ax + b) = (65235 .38) . but. a and b are not . To convert the message point (65235 .38) on E back to its original message [3] Now both Alice and Bob compute the secret key abP E E .. and use it fo r number m . we just comput e further secure communications . n = [65235/30J = [2174 .5] = 2174 . There is no known fast way to compute abP if one only knows P . aP an d bP – this is the discrete logarithm problem on E . [2] Multiply Points on Elliptic Curves over Fq : We have discussed the calcu- lation of kP E E over Z/NZ . In elliptic curve public-key cryptography. (2) Analogue of the Massey–Omura Cryptosystem : we are now interested in the calculation of kP E E over F,, . which can b e done in 0(logk(logq) 3 ) bit operations by the repeated doubling method. [1] Alice and Bob publicly choose an elliptic curve E over Fq with q large , and we suppose also that the number of points (denoted by fi) is publicl y known . [2] Alice chooses a secret pair of numbers (e i . (1n) such that daen = 1 ( mo d N) . Similarly, Bob chooses ((ra, dn) .

3 . Applied Number Theory in Computing/Cryptography 3 .3 Crvptogra ry and Information Security 38 3 382 [3] If Alice wants to send a secret message-point P E E to Bob, the procedure Exercise 3 .3 .9 . Work back from the descriptions of the elliptic curve ana- is as follows : logues of the ElGamal and the Massey–Omura cryptosystems discusse d [3-1] Alice sends e ;1 P to Bob . above . to give complete algorithmic descriptions of the original ElGamal an d [3-2] Bob sends e B e 4 P to Alice . the original Massey–Omura public-key cryptosystems . [3-3] Alice sends dae B e,4 P = e B P to Bob . (IV) Menezes-Vanstone Elliptic Curve Cryptosystem . A seriou s problem with the above mentioned elliptic curve cryptosystems is that, th e [3-4] Bob computes d B f B P = P . plaintext message units in lie on the elliptic curve E . and there is no conve- nient method known of deterministically generating such points on E . Fortu- Note that an eavesdropper would know e 1 P . e B e ,aP . and e B P . So if nately . Menezes 17 and Vanstone is had discovered a more efficient variation he could sol ve the discrete logarithm problem on E, he could determine C B [156] : in this variation which we shall describe below . the elliptic curve i s from the first two points and then compute dB = ef] 1 mod V and hence ge t P = d B (e B P) . iuns1eFd„fxors`\"mraatshkeirngth\"a, nanodnththeepelalliinptteixctcaunrdvec.iphertext pairs are allowed to b e (3) Analogue of the ElGamal Cryptosystem : [1] Preparation : Alice and Bob publicly choose an elliptic curve E over F,, , with p > 3 is prime and a random base point P E E(FI,) such that P [1] Alice and Bob publicly choose an elliptic curve E over Fq with q = p ' generates a large subgroup H of E(Fp ), preferably of the same size a s and p E Primes, and a random base point P E E . that of E(Fp ) itself. Assume that randomly chosen k E ZIBI and a E N are secret . [2] Alice chooses a. random integer r,, and computes 1 .0 P ; Bob also choose s a random integer r b and computes r b P . [2] Encryption : Suppose now Alice wants to sent messag e [3] To send a message-point M to Bob . Alice chooses a random integer k and sends the pair of points (kP, 3I + k(r t P)) . [4] To read 1d . Bob compute s i + k(r 1 P) - re (kP) = (3 .90 ) m = (m i ,m 2 ) E (Z/pZ)* x (Z/p7Z)* (3 .91 ) An eavesdropper who can solve the discrete logarithm problem on E can . to Bob . then she does the following : of course . determine r b from the publicly known information P and ri P . Bu t as everybody knows . there is no efficient way to compute discrete logarithms , [2-1] 3 = aP . where P and 3 are public . so the system is secure . 17 (4) Analogue of the RSA Cryptosystem : Alfred .J . Menezes is a professor of mathematics in the Department R .SA, the most popular cry ptosystem in use, also has the following ellipti c of' Cmnbinatorics and Optimization at the University of Water - curve analogue : loo, where he teaches courses in cryptography, coding theory, finit e fields . and discrete mathematics . He is actively involved in crypto - [1] 'G = pq is a public key which is the product of the tR o large secret prime s graphic research, and consults on a regular basis for Certicom Corp . . p and q . He completed the Bachelor of Mathematics and M .Math degrees i n 1987 and 1989 respectively, and a Ph .D . in Mathematics from th e University of Waterloo (Canada) in 1992 . [2] Choose two random integers a and b such that E : = .r' ; + ax + b Scott A . Vanstone is one of the founders of Certicom . the first com - defines an elliptic curve both mod p and mod q . pany to develop elliptic curve cryptography commercially . He devote s mrch of his research to the efficient nnplementation of the ellipti c [3] To encrypt a message-point P, just perform eP mod V where e is the curve cryptography for the provision of information security service s public (encryption) key . To decrypt, one needs to know the number of in hand-held computers . smart cards . wireless device s ; and integrated points on E modulo both p and q . circuits. A'anstone has published more than 150 research papers and several hooks on topics such as cryptography, coding theory, finit e The above are some elliptic curve analogues of certain public key crvp- fields, finite geometry; and combinatorial designs . Recently, he wa s tosv steins . It should be noted that almost every public-key crvptosystem ha s elected a Fellow of the Royal Society of Canada . t \" anstone received a Ph .D . in an elliptic. curve analogue; it is of course possible to develop new elliptic curv e mathematics from the University of Waterloo in 1974 . cryptosystems which do not. rely on the existing cryptosystems .

3 . Applied \\l umber Theory in Comp 1g/Cryptography 3 .3 Cryptography and Information Security 38 5 384 [2-2 ] (T ' Y2) = k 3 3 .3 .9 Digital Signature s [2-3] co = kP . [2-4] cj _ yi n? ) (mod p) for j = 1, 2 . The idea of public-key cryptography (suppose we are using the RSA public - key scheme) can also be used to obtain digital signatures . Recall that i n [2-5] Alice sends the encrypted message c of m to Bob : public-key cryptography. we perform c = (co .ci,( .z) . (3 .92 ) [3] Decryption : Upon receiving Alice's encrypted message c, Bob calculate s C=E,„(11) . (3 .93 ) the following to recover rn : [3-1] aco = (T ; Yt 2) . where 111 is the message to be encrypted, for message encryption, an d [3-1] rn = (c r'.p a (mod p), c 2 y ., (mod p)) . 11=D,1,(C) , (3 .94 ) Example 3 .3 .11 . The following is a nice example of Menezes Vanston e crvptosystem, taken from [16 .5] . where C is the encrypted message needed to be decrypted .. for decryption . In digital signatures . we perform the operations in exactly the opposite direction . [1] Key generation : Let E be the elliptic curve given by y 2 = a; 3 + 4x + 4 That is, we perform (see also Figure 3 .11 ) over ]F13 , and P = (1 .3) be a point on E . Choose E(Fr 3 ) = H which is cyclic of order 15, generated by P . Let also the private keys k = .5 an d S = D d (31), (3 .95 ) a = 2 . and the plaintext rn = (12 .7) = (mr, m2) . where ill is the message to be signed, for signature generation , (3 .96) [2] Encryption : Alice computes : M = Ee k. (S), = aP = 2(1 .3) = (12 .8 ) where S is the signed message needed to be verified, for signature verification . (yr, y2 ) = k/3 = 5(12,8) = (10,11 ) Suppose now Alice wishes to send Bob a . secure message as well as a digita l co = kP = .5(1 .3) = (10,2 ) cr - yrmr = 10 . 2 E 3 (mod 13 ) Public and also insecur e Cryptanalyst/Enemy c2= y2m2= 11 7- 12 (mod 13) . channel Al ' Then Alice sends Messag e Signin g Verificatio n lessag e M S=Dd,, ( 31 ) Al = E, .. ( S ) c = (co, cr, c2 ) = ((10, 2) .3, 12 ) Key source 1 Key- source 2 to Bob . Decryption key Encryption key [3] Decryption : Upon receiving Alice's message, Bob computes : (Private key) (Public key ) aco = 2(10 .2) = (10 .11) = (yr, y 2 ) rnu = cry[ r = 12 (mod 13 ) Figure 3 .11 . Digital signatures in, = c2 yz u = 7 (mod 13) . signature . Alice first uses Bob ' s public key to encrypt her message . and then , Thus . Bob recovers the message in = (12 . 7) . she uses her private key to encrypt her signature, and finally sends out he r We have introduced so far the most popular public-key cryptosystems , such as Diffie-Hellman-Merkle, RSA . Elliptic curve and probabilistic cryp- tosystems . There are, of course . many other types of public-key crtiptosys- tenis in use, such as Rabin . -11cEliece and Knapsack cryptosystems . Reader s who are interested in the cryptosystems which are not covered in this boo k are suggested to consult Menezes et al . [157] .

3 . Applied Number Theory in Computing/Crti ptogral 3 .3 Cryptography and Information Security 38 7 386 Decryption of SB Public and insecur e message and signature to Bob . At the other end . Bob first uses Alice's publi c SB = Ill\" mod N B channe l key to decrypt Alice's signature, and then uses his private key to decryp t Alice's message . Figure 3 .12 shows how A (Alice) and B (Bob) can sen d TT \"B = SI/' mod NB secure message/signature to each other over the insecure channel . Decryption of MB Encryption of S u Example 3 .3 .12 (Digital Signature) . To verify that the $100 offer in Ex - ample 3 .3 .8 actually carne from RSA, the following signature was added : TIB = CH { mod :1 , 1 -y B  j1 ')i ' mod ' . S = 167178611503808442460152713891683982454369010323583112178 _ Encryption of RIB 350384469290626554487922371144905095786086556624965779748 _ 40004057020373 . It was encrypted by S = 11 .0 ( mod N) . where d is the secret key, as in Exam- ple 3 .3 .8 . To decrypt the signature, we use ll7 = S i (mod N) by performin g the following procedure (also the same as in Example 3 .3 .8) : B's Message RIB B's Message MB C1 and Signature SB j and Signature S B e = (10001100101111) 2 0\\Ie,sage B /Sign atm B for i from 1 to 14 d o < C C 2 mod N ife[i]=0then C-C*xllmod N print C Alice (e .i .NA ,d A ,C .N3 Bob ( eB . NB,dB . co . NA ) which gives the following decrypted text : 6091819200019151222051800230914190015140500082114 _ 041805040004151212011819 . A's Message AlA A's Message 17,1 It translates t o and Signature SA and Signature SA FIRST SOLVER WINS ONE HUNDRED DOLLAR S Encryption of RIA Since this signature was encrypted by RSA's secret key, it cannot be forged by an eavesdropper or even by R.SA people themselves . Decryption of R h In Example 3 .3 .12 . the signature is a different text from the message . and usually is appended to the encrypted message . We can . of course directly sig n 4 = S,A mod N a Sa = 1I7,'' mod A A the signature on the message . This can be done in the following way . Suppos e Decryptio A (Alice) wants to send B (Bob) a signed message . Suppose also tha t Public and insecur e channel [1] Alice (A) has her own public and secret keys (e,1. , NA ; d 1 ) as well as B' s public' key eB and NB from a public domain ; Figure 3 .12 . Sending encrypted messages and signatures using the RSA sche n (the encrypted message and the signature are two different texts) [2] Bob (B) has his own public and secret keys (eB .NB ;dB) as well as A' s public key- ea and N4 from a public domain . To send a signed message from A to B : [1] Alice uses B ' s public key CB and NB to encrypt her message 11 1 : C .1 = 11 `,x\" mod NB . (3 .97)

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 38 9 388 [2] Alice signs the message using her own secret key d A directly on the Public and insecur e encrypted message : channe l S 4 = C `a a mod N 1 . (3 .98 ) Decrypt signature and sends this signed message to B over the network . Upon receiving As signed message .. CH = SB mod NB SB = C mod NB [1] B uses A's public key c 1 to decrypt As signature : Decsvptio Signatur e C4 = S`,'{' mod N4 . (3 .99 ) [2] B further uses his own secret key d B to decrypt AS encrypted message : MB = CB' mod NA C B = 5l mod 11 4 = C ` \" mod _\\'B . (3 .100 ) l 1, B's message M B Encryptio n In this way . Bob can make sure that the message he has just received indee d Ws Message MB B's Message AIB comes from A . since the signature of A's message is encrypted by A's ow n secret key, which is only known to A . Once the message is sent out . A canno t 4 { Signed Message B deny the message . Similarly. Bob can send a signed message to Alice . The V above process is shown in Figure 3 .13 . Alice (CA,1VA,dA,eB,NB) Bob ( e B, d B, e a, N A ) Example 3 .3 .13 (Digital Signature) . Suppose now Alice wants to send As Message MA AB Bob the signed message \"Number Theory is the Queen of Mathematics\" . Th e Signed Message process can be as follows : I A's Message 1114 [1] Suppose Alice has the following information at hand : Encryption A 's message 11A CA = 11i,\" mod NB I MA = 1421130205180020080515182500091900200805001721050514001 _ 4 = C ` \" mod NB 50600130120080513012009031 9 Sign atu e Decryption NA = 1807082088687404805951656164405905566278102516769401349 _ 1701270214500566625402440483873411275908123033717818879 _ = 'A mod NA = Sa mod A'4 66563182013214880557 (130 digits ) Decrypt signature 3968599945959745429016112616288378606757644911281006483 _ 2555157243 . 45534498646735972188403686897274408864356301 _ 26320506960099904459 9 c t = 261 7 dA = 9646517683975179648125577614348681987353875490740747744 _ 710230985275797178884880163 .711139144032242624779107574 _ 09230 .50236448593109 and suppose Bob has the following information at hand : Public and insecure channe l NB = 1143816257578888676692357799761466120102182967212423625 _ 6256184293570693524573389783059712356395870505898907514 _ Figure 3 .13 . Sending encrypted and signed messages using the RSA scheme (th e 7599290026879543 .541 (129 digits ) signatures are directly made on the encrypted message ) = 3490529510847650949147849619903898133417764638493387843 _ 990820577 . 327691329932667095499619881908344614131776429 _ 67992942539798288533

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 39 1 390 CB= 900 7 Remark 3 .3 .9 . Suppose Bob is sending an encrypted message to Alice . Nor- mally. the encrypted message consists of a number of blocks : one of the blocks d B = 1066986143685780244428687713289201547807099066339378628 _ is Bob's signature . Alice can easily identify which block is the signature block. 0122622449663106312591177447087334016859746230655396854 _ since the ordinary decryption procedure for that block yields gibberish . I n 451327710905360609 5 practice . there are two ways for constructing Bob's encrypted signature (Den - son [60]), depending on the values of the moduli n B and nA : [2] Alice first encrypts the message M4 using eB and 3 o get (1) If n A < nB, then C A = MA\" mod NB S B = Ol d ' mod n 3)e,t mod ii A, 11B = ( Sd=' mod nA)e\" mod n B . n the following process : The inequality 71A < 17B ensures that the expression in the parentheses CA1 is not too large to be encrypted by Alice's encryption key . CB (10001100101111) 2 (2) If n A < nB, then for from 1 to 14 do 1114 mod NB SB = (11mod nA) d\" mod n B , MB = ( S\" mod n B ) d' mod it 4 . CAC modN13 if e B [i] = 1 then C4 +- C A The inequality n A > n B ensures that the expression in the parenthese s Save CA is not too large to be encrypted by Bob ' s decryption key. [3] Alice then signs the message C1 using d A and NA to get S,t C, `1 mo d The above mentioned signature scheme is based on RSA cryptosystem . NA via . the following process : Of course . a signature scheme can be based on other cryptosystem . In wha t follows, we shall introduce a very influential signature scheme based of E1Ga- SA f 1 mars cryptosystem [69] ; the security of such a signature scheme depends o n the intractability of discrete logarithms over a finite field . d A <— (10110010 - . .11010101) 2 for i from 1 to 429 d o Algorithm 3 .3 .5 (ElGamal Signature Scheme) . This algorithm tries t o generate digital signature S = (a . b) for message rn . Suppose that Alice wishes S A SA mod _y\",r to send a signed message to Bob . if dA [1,i] = 1 then SA f- SA • Ca mod N A Send SA [4]Upon receiving Alice ' s message, Bob first decrypts Alice ' s signature usin g [1] [ElGamal key generation] Alice does the following : CA and N3. to get CA = Si r mod NA via the following process : [1-1] Choose a prime p and two random integers g and x, such that bot h CA f 1 g and J. are less than p . cA (101000111001) 2 for i from 1 to 12 d o [1-2] Compute y = g` (mod p) . Ca CA mod NA [1-3] Make (y .g .p) public (both g and p can be shared among a group of if eA[i] = 1 then CA f- CA . S A mod NA users), but keep J. as a secret . Save CA [5] Bob then decrypts Alice's message using d B and N B to get 1la = [2] [ElGamal signature generation] Alice does the following : Cag mod NB via the following process : 17,a<- 1 [2-1] Choose at random an integers k such that gcd(k, p — 1) = 1 . d B := (1001110110 . -1001110 2 [2-2] Compute for i from 1 to 426 d o a = (mod p), 114 ;ll mod N B 1d A . CA mod NH b k—r (in xa) (mod (p — 1)) . (3 .101 ) if dB[i] = 0 then MA print :11;1

3 . Applied Number Theory in Computing/Cryptograph 3 .3 Cryptography and Information Secu rity 39 3 392 Now Alice has generated the signature (a .. b) . She must keep the rando m [1-3] Generate an element g E /pZ whose multiplicative order is q, i .e . , integer, k, as secret . y 9 - 1 (mod p) . [3] [ElGamal signature verification] To verify Alice's signature, Bob confirm s [1-4] Find a one-way function H mapping messages into 160-bit values . that [1-5] Choose a secret key x, with 0 < .r < q , °' (mod p) . (3 .102 ) [1-6] Choose a public key y, where y fi t (mod p) . Clearly, the secret :r is the discrete logarithm of y, modulo p, to the base y . 3 .3 .10 Digital Signature Standard (DSS ) [2] [DSA Signature Generation] To sign the message rn, the sender produces hi s In August 1991, the L .S . government's National Institute of Standards an d signature as (r, s), by selecting a random integer k E 7L/qZ and computin g Technology (KIST) proposed an algorithm for digital Signatures . The al- gorithm is known as DSA . for Digital Signature Algorithm . The DSA has r = (y r (niod p)) (mod q), (3 .103 ) become the L .S . Federal Information Processing Standard 186 (FIPS 186) . s - k r (H(m) + x r) (mod q) . It is called the Digital Signature Standard (DSS), and is the first digita l signature scheme recognized by any government . The role of DSA/DSS is ex- [3] [DSA Signature Verification] To verify the signature (r .$) for the message pected to be analogous to that of the Data Encryption Standard (DES) . Th e rn from the sender, the receiver first computes : DSA/DSS is similar to a signature scheme proposed by Schnorr [220] ; it i s also similar to a signature scheme of ElGamal [69] . The DSA is intended fo r t - s —' (mod q), (3 .104) use in electronic mail, electronic funds transfer, electronic data interchange . software distribution, data storage, and other applications winch require dat a and then accepts the signature as valid if the following congruence holds : integrity assurance and data authentication . The DSA/DSS consists of two main processes : r (gxlmhy''c (mod p)) (mod q) . (3 .105 ) (1) Signature generation (using the private key) , If the congruence (3 .105) does not hold, then the message either may hav e been incorrectly signed, or may have been signed by an impostor . In thi s (2) Signature verification (using the public key) . case, the message is considered to be invalid . A one-way hash function is used in the signature generation process to obtai n There are, however . many responses solicited by the (US) Associatio n a condensed version of data, called a message digest . The message digest i s of Computing Machinery (ACM) [45] . positive and negative, to the NIST' s then signed . The digital signature is sent to the intended receiver along wit h DSA . Some positive aspects of the DSA include : the signed data (often called the message) . The receiver of the message an d the signature verifies the signature by using the sender's public key . The same (1) The U .S . government has finally recognized the utility and the useful- hash function must also be used in the verification process . In what follows , ness of public-key cryptography . In fact, the DSA is the only signature we shall give the formal specifications of the DSA/DSS . algorithm that has been publicly proposed by any government . Algorithm 3 .3 .6 (Digital Signature Algorithm . DSA) . This is a vari- (2) The DSA is based on reasonable familiar number-theoretic concepts . and ation of ElGamal signature scheme . It generates a signature .9 = (r,$) for th e it is especially useful to the financial services industry . message rn . (3) Signatures in DSA are relatively short (only 320 bits), and the ke y [1] [DSA key generation] To generate the DSA key, the sender performs th e generation process can be performed very efficiently. following : [1-1] Find a 512-bit prime p (which will be public) . (4) When signing . the computation of r can be done even before the messag e rn is available, in a \" precolnputation \" step . [1-2] Find a 160-bit prime q dividing evenly into p—1 (which will be public) . Whilst some negative aspects of the DSA include : (1) The DSA does not. include key exchanges . and cannot be used for ke y distribution and encryption .

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 39 5 394 (2) The key size in DSA is too short : it is restricted to a 512-bit modulu s [3-2] verify that (r, s) are integers in the interval [1 . q 1], compute s or key size . which is too short and should be increased to at least 102 4 kP = (r i .yr), and r x i (mod q) . bits . [3-3] compute in = s-r (mod q) and H(rn) . (3) The DSA is not compatible with existing international standards : for example, the international standards organizations such as ISO . CCITT [3-4] compute ur = H(m)w (mod q) and 112 = rzc (mod q) . and SWIFT all have accepted the RSA as a standard . [3-5] compute u 1 P + u 2 Q = (xo . yo) and v - r 0 (mod q) . Nevertheless, the DSA is the only one publicly known government digita l [3-6] accept the signature if and only if m = r signature standard . Exercise 3 .3 .10 . Try to develop an elliptic curve analogue of an existin g \\\\e have already noted that almost every public key cryptosystem has a n signature scheme that you are familiar with for obtaining and checking digita l elliptic curve analogue . It should also be noted that digital signature scheme s signatures . can also be represented by elliptic curves over IF,, with q a prime power o r over Z /nZ with n = pq and p, q E Primes . In exactly the same way as that fo r 3 .3 .11 Database Securit y public-key cryptography, several elliptic curve analogues of digital signatur e schemes have already been proposed (see . for example, Meyer and Miiller Databases pose a special challenge to the designer of secure information sys- [160]) . In what follows we shall describe an elliptic curve analogue of the DSA/DSS . called ECDSA. tems . Databases are meant to be shared . The sharing is often complex. In Algorithm 3 .3 .7 (Elliptic Curve Digital Signature Algorithm) . Let many organizations, there are many \"rules\" concerning the access to different E be an elliptic curve over F,, with p prime, and let P be a point of prime orde r q (note that the q here is just a prime number, not a prime power) in E(IFp ) . fields (or parts) of a database . For example, the payroll department may hav e Suppose Alice wishes to send a signed message to Bob . access to the name, address and salary fields . while the insurance office may [1] [ECDSA key generation] Alice does the following : have access to the health field of an individual . In this subsection . we shal l [1-1] select a random integer E [1 . q 1] , introduce a method for database protection : it encrypts the entire databas e [1-2] compute Q = .rP , but the individual fields may be decrypted and read without affecting th e [1-3] make (2 public, but keep .r as a secret . Now Alice has generated the public key Q and the private key r . security of other fields in the database . [2] [ECDSA signature generation] To sign a message rn, Alice does the following : Let [2-1] select a random integer k E [1 . q 1] , D = (F1 . F2 F) (3 .106) [2-2] compute AT = (r i ,yjr), and r - rr (mod q) . If r = 0, go to ste p where D is the database and each Fa is an individual file (or record) . As i n [2-1] . R.SA encryption, each file in D can be regarded as an integer . To encrypt [2-3] compute k-t mod q . D . we first select n distinct primes m 1 .11 1 2 . . . where m., > for [2-4] compute .s k -r (H(nc) + xr) (mod q), where H(m) is the has h value of the message . If s = 0, go to step [2-1] . i = 1, 2 n . Then by solving the following system of congruences : The signature for the message in is the pair of integers (r, s) . C Fr (mod rn i ) . C F, (mod m2) . [3] [ECDSA signature verification] To verify Alice's signature (ins) of the mes- sage in, Bob should do the following : (3 .107 ) [3-1] obtain an authenticated copy of Alice ' s public key (2 : C = F„ (mod m„), j we get C . the encrypted text of D . According to the Chinese Remainder Theorem, such a C always exists and can be found . Let lI = 117170 2 (3 .108 ) 31-[ = .ld/rn ;, e ; = 7h4 [11I; 1 mod m.

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 39 7 396 for i = 2, - . , n . Then C can be obtained as follows : Part I1 : Database Decryption . At this stage, the database user L-, is suppose d to have access to the encrypted database C as well as to have the read-ke y C = e . F (mod 11) . 0 < C < H . (3 .109) m,, so he performs the following operation : F, - C (mod rig), 0 < F, < rn, . (3 .113) The integers e1 .e2,''--e,, are used as the write-keys . To retrieve the i-t h The required file F, should be now readable by user C, . file F, from the encrypted text C of D . we simply perform the following operation : Example 3 .3 .14 (Database Encryption and Decryption) . Let F, - C (mod m;), 0 < F, < m, . (3 .110 ) F .The moduli m i , m2 . .m,, are called the read-keys. Only people knowing D = (F1 . F2 i F3 . F4, F5 ) = (198753 .217926,357918,377761 .391028) . the read-key rn, can read file but. not other files . To read other files, for example, F,+2, it is necessary to know a read-key other than m i . We present Choose five prunes rnr, m2 . m 3 . m4 and rn, as follows : in the following an algorithm for database encryption and decryption . Algorithm 3 .3 .8 (Database protection) . Given D = (Fr,F2 , . . . ,F,,) , mr = 35037 7 > Fr = 198753 , this algorithm will first encrypt the database D into its encrypted text C . To m2 = 36442 3 > F2 = 217926 . retrieve information from the encrypted database C, the user uses the appropri - 1173 = 37612 7 > F2 = 357918 , ate read-key m, to read file F, : m 4 = 38921 9 > F4 = 377761 , m 5 = 391939 > F5 = 391028 - Part I : Database Encryption . The database administrators (DBA) perform th e following operations to encrypt the database D : According to (3 .111), we have : [1] Select n distinct primes m t , rn2 , • - - , mn with m, > F,, for i = 1, 2, . .n . C = Fi (mod m,r) > C - 198753 (mod 350377 ) C F2 (mod m2 ) > C ° 217926 (mod 364423 ) [2] Use the Chinese Remainder Theorem to solve the following system o f C F3 (mod 117 3 ) > C 357918 (mod 376127 ) congruences : C F4 (mod m4) > C 377761 (mod 389219 ) C Fr (mod mr) , C F5 (mod m 5 ) > C 391028 (mod 391939) . C F2 (mod m2) . (3 .111 ) Using the Chinese Remainder Theorem to solve the above system of congru- ences, we get and get C F,, (mod m„) . C = ej Fj (mod 17), 0 < C < M C = 5826262707691801601352277219 . (3 .112 ) Since 0 < C < Al with where nd = mtm2 . . . 111 = 350377-364423W376127 . 389219 39193 9 _1I, = M/mi . = 7326362302832726883024522697 , e=AI,[11 ' mod r n C is the required encrypted text of D . Now suppose user Lr2 has the read-key 1712 = 364423 . Then he can simply perform the following computation an d fori=1 .2, .' .rz . get F2 : [3] Distribute the read-key rn, to the appropriate database user C, . F> C (mod m,) . Now C (mod m 2 ) = 5826262707691801601352277219 mod 36442 3 = 217926 = F, .

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 39 9 398 which is exactly what the user U9 wanted . Similarly, a user can read F5 if h e rrt i = 9901 > F l = 9853 , knows rn 5 , since m2 = 7937 > F7 = 6792 . m3 = 5279>F3 =3761 .. C (mod in,) = 5826262707691801601352277219 mod 39193 9 rn4 = 6997 > Fi = 5102 . 39102 8 F5 (1) What are the four write keys e I . C2 . C and e 4 used in the encryptio n process ? Remark 3 .3 .10 . In Example 3 .3 .14 . we have not explicitly given the com- puting processes for the write keys et and the encrypted text C : we give now (2) What is the encrypted text C corresponding to D ? the detailed computing processes as follows : (3) If F] is changed from FI = 9853 to Fr = 9123, what is the new value of ei = 1llr • (AM-ri mod rn i ) the encrypted text C ? = 20909940729079611056161•(2090994072907961105616 1 -1 mod 350377 ) To protect a database, we can encrypt it by using encryption keys . To protect encryption keys, however, we will need some different methods . In th e = 304057721123765348250953949 3 next subsection, we shall introduce a method for protecting the cryptographi c C2 = Ah (Al i mod 7rt2 ) keys . = 20104006341072673467439•(2010400634107267346743 9 -1 mod 364423 ) = 2830382740740598479460334493 c 3 = M3 (W I mod rn 3 ) = 19478426975018349873911•(1947842697501834987391 1 -i mod 376127 ) 3 .3 .12 Secret Sharin g = 199188342089235147645601277 1 Liu [145] considers the following problem : eleven scientists are working on a secret project . They wish to lock up the documents in a cabinet such that th e e 4 = 1yI3 (Al l mod 77x4 ) cabinet can be opened if and only if six or more of the scientists are present . = 18823239109171769320163•(1882323910917176932016 3 —1 mod 389219 ) What is the smallest number of locks needed? What is the smallest numbe r of keys to the locks each scientist must carry? The minimal solution uses 46 2 = 606802876838459410397162614 7 locks and 252 keys . It. is clear that these numbers are impractical, and the y become exponentially worse when the number of scientists increases . In this e 5 = AI5 mod 70 5 ) section, we shall introduce an interesting method to solve similar problems . It is called secret sharing and was first proposed by Shamir in 1979 (se e = 18692608550903908217923 . (18692608550903908217923 -i mod 391939 ) Mignotte [161] and Shamir [225]) . The method can be very useful in the management of cryptographic keys and the keys for accessing the passwor d = 721852464410256223651532491 . file in a computer system . So Definition 3 .3 .4 . A (k,71)-threshold scheme is a. method for n people (or parties) P, . Pz i . . • ,P,, to share a secret S in such a way that the followin g C (eiFi + e 2 F7 + e 3 F3 + e4F4 + e5 F5 ) mod A I properties hold : (3040577211237653482509539493 . 19875 3 (1) k < 7t . + 2830382740740598479460334493 - 21792 6 + 19918834208923 .51476456012771 - 35791 8 (2) each P, has some information I„ + 6068028768384594103971626147- 37776 1 (3) knowledge of any k of the IF ,12 , • • ' ; I„ } enables one to find S easily. + 721852464410256223651532491 . 391028 ) (4) knowledge of less than k of the {11 .12 .'' . , I, } does not enable one t o mod 7326362302832726883024522697 find S easily . 5826262707691801601352277219 . Of course, there might be several ways to construct such a threshold Exercise 3 .3 .11 . Let the database D be scheme . but perhaps the simplest is the one based on congruence theory and the Chinese Remainder Theorem . It can be shown (Krana [134]) by th e D = (Fi .F2 .F3 .Fl Chinese Remainder Theorem that : = (9853, 6792 .3761 .5102) . and the four read keys b e

3 . Applied Number Theory in Computing/Cryptograph y 3 .3 Cryptography and Information Security 40 1 400 Theorem 3 .3 .3 . For all 2 < k < n, there exists a (k, n)-threshold scheme . [2] Combine all the to get the secret S : In what follows_ we shall introduce an algorithm for constructing a (k, n) - S = E Si, k (3 .119 ) threshold scheme . 3=1 mod m,, . Algorithm 3 .3 .9 (Secret sharing) . This algorithm is divided into two parts : 1 ,) the first part aims to construct a secret set {11 .12 . . . . 1,z }, whereas the secon d part aims to find out the secret S by any A. of the {1 1 .72 , . . . . I,,} . Throughou t (By the Chinese Remainder Theorem, this computed S will be the re- the algorithm, S denotes the secret . quired secret) . Part I : Construction of the secret set {I4,12 , Example 3 .3 .15 . Suppose we wish to construct a (k, n)-threshold scheme with A. = 3 and n = 5 . The scheme administrator of a security agency firs t [1] Let the threshold sequence rn t ,m 2 , • • • , m„ be positive integers > 1 defines the following threshold sequence m, : such that gcd(m, in j ) = 1 for i j an d m t = 97 , mrn2 . . . 0 k m ,z–x+2 . (3 .114 ) m 2 = 98 , m 3 = 99 , [2] Determine the secret S in such a way tha t m4 = 101 . nt 5 103 , max(k – 1) < S < min(k) (3 .115 ) and computes : (3 .116 ) where min(k) = MI m9 • . .Mk , M = m 1 m 2m 3 m 4rn5 = 9790200882 max(k – 1) = m„m„– 1 min(k) = m 1 m2 m, 3 = 94109 4 max(k – 1) = m4 m 5 = 10403 . He then defines the secret S to be in the range [3] Compute {11,12 1„, } in the following way : 10403 < S = 671875 < 94109 4 S (mod rn i ) , and calculates each I for each P, : S - 12 (mod m 2 ) , S-I1 (mod m i ) > 11 =5 3 (3 .117 ) S - 12 (mod m2 ) > 12 = 85 S- 13 (mod m3 )--> 13 = 6 S - (mod m„) . S E 14 (mod m4 ) 14 = 2 3 5-I5 (mod m ;5)–>15=6 . [4] Compute M = m i me - m„ . [5] Send I, and (m,, M) to each P; . Finally he distributes each I, as well as m i and Al to each P,, so that each P; who shares the secret S has the triple (I, . rn„ AI) . Part II : Recovering S from any k of these 11 ,12 . - . I„ : Suppose now partie s Suppose now P1 , P2 and P3 want to combine their knowledge {I1,12 .13 } {Pi, .Pr 2 , . ,} want to combine their knowledge {I„,I,, .---,1,,_} t o to find out, S . They first individually compute : n has the triple (I,,, m, , , 1I) at hand) . find out S . (Each P,,, j = 1 .2 171 = M/rn t = 10092990 6 AI2 = A1/m 2 = 99900009 [1] Each P,,, j = 1, 2, - - - .k computes his own secret recovering key Si , AI3 = M/m 3 = 9889091 8 as follows : Al = Al/m,. and 1> _ _ll 1 (mod \\'1 - 'lli 1 (mod rrr t ) > 1\"1 = 9 5 S, = 1,,A1,,1\\', _ . (3 18) N- EE- _11. -;1 (mod m 2 ) > N2 =1 3 N3 = A13-I (mod rn3) N = 31 .

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 40 3 402 Hence, they get (I,,tnr) = (824,1501 ) (12i m>) = (1242 .1617) S Ir - I - N3 +12 112 -N2 +I3 _13 ti3 (modni l 2 m 3) (13 . rn3) = (1602,1931) 53 100929906 - 95 + 85 - 99900009 . 13 + 61 - 98890918 3 1 (1r,m4) = (1417,5573) (mod 97 - 98 . 99 ) (I5 , ni . ) = (3090, 6191 ) 805574312593 (mod 941094 ) (I6 .m.6 ) = (281,7537 ) 671875 . (17 ,rn 7 ) = (6261,9513) 11 =1501 . 1617 . 1917 . 3533 . 9657 . 10361 . 5311 3 Suppose . alternatively. P,P and P5 wish to combine their knowledge {I 3 .I I . I } to find out S . They do the similar computations as follows : = 1159414813752079260508694 1 lIr = 11/m l = 10092990 6 Now suppose parties P . P3 . P,. P6 , P wish to combine their knowledg e lIt = .lI/rn4 = 9693268 2 {Ir .I3-15,16 .17} to find out S . What is the S? Suppose also partie s 115 = AI/rn 5 = 9505049 4 P . P3 , Pt . P3 , P6 wish to combine their knowledge {12 ,15 , 14 .15 .16 to fin d out S . What is the S then? (The two S's should be the same . ) and \"i = lIi r (mod > N4I=96'15 3 .3 .13 Internet/Web Security and Electronic Commerc e Therefore . N4= .lJ t (mod menI3)) > N5 = 100 . _N5 ) 11;, (mod m 5 ) It is easy to run a secure computer system . You merely have to disconnect all dial-up connections and permit only direct-wired terminals, put th e S Ir•IIr-Nr+Ir•i11,-N 1 +15 -415 -N5 (mod rn 3 •m4 -m 5 ) machine and its terminals in a shielded room, and post a guard at th e 53 - 10092990 6 . 95 + 23 - 96932682 . 61 + 6 . 95050494 . 10 0 door . (mod 97 • 101 - 103 ) 70120892 .59 .56 (mod 1009091 ) C*R.AMMPP AND MORRI S 671875 . UNIX Operating System Security [91] However, knowledge of less than 3 of these Ir , I2 , ,I4 .I5 is insufficient t o find out S . For example, you cannot expect to find out S just by combinin g The security mentioned in the above quotation is unfortunately not what we Il and I4 : need, though it is easy to achieve : an isolated and disconnected compute r system is essentially a useless system in modern days . We would like such a S' = II . AIt •Nr+74-_llr•N4 (mod ntr . m 4 ) (local network) system which is fully connected to the Internet but still be a s 53 • 10092990 6 . 95 + 23 . 9693268 2 . 61 (mod 97 - 101 ) secure as a disconnected system . How can we achieve such a goal? The first 644178629556 (mod 9791) method to secure the local system is to introduce a firewall (security gateway ) 5679 . to protect a local system against intrusion from outside sources . An Internet firewall serves the same purpose as firewalls in buildings : to protect a certai n Clearly, this is not the correct value of S . Of course, you can find out S by area from the spread of fire and a potentially catastrophic explosion . It i s any 3 or more of the It .12 .13 .14 .15 . used to examine the Internet addresses on packets or ports requested on incoming connections to decide what traffic is allowed into the local network . Exercise 3 .3 .12 . In the above context, find out S if Pi . P3 . P4 . P; wish t o The simplest form of a firewall is the packer filter . as shown in Figure 3 .14 . combine their knowledge {1r .13 .14 . I5 } to find out S . It basically keeps a record of allowable sources and destination IP addresse s and deletes all packets which do not have these addresses . Unfortunately, thi s Exercise 3 .3 .13 . Suppose a security agency defines a (5, 7)-threshol d firewalling technique suffers from the fact that IP addresses19 can be easily scheme and sends each triple (I„ rn„ AI) defined as follows to each perso n forged . For example, a \"hacker\" might determine the list of good sourc e P , for i = 1, 2, - - - , 7 . who shares the secret S : addresses and then acid one of these addresses to any packets which ar e addressed into the local network . Although some extra layers of security can 19 An Internet Protocol address (IP address), or just Internet address, is a uniqu e 32-bit binary number assigned to a host and used for all commmnication wit h the host .

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Security 40 5 404 Allowable outgoin g Local Loca l Router with Loca l IP addresse s network network Encryptio n networ k Firewall Local an d Local network Decryption network Allowable Incomin g 1P addresses • Internet • • • Local Router with • network Loca l Encryption network Local an d network Decryption Figure 3 .14 . Packet filter firewalls Figure 3 .15 . Cryptographic tunnel s be added into a firewall, it is generally still not powerful enough to protect a development of the cryptographic tunnels is the Virtual Private Network s local system against intrusion from outside unfriendly users in the Internet . technologies [264], which use tunneling to create a private network so as t o It is worthwhile pointing out that all networked systems have holes in the m keep communication private . by which someone else can slip into . For example, recently the U .S . Federal Bureau of Investigation (FBI) estimated that $7 .5 billion are lost annually t o Cryptographic tunnels have important applications in secure communica- electronic attack and the U.S . Department of Defence (DOD) says that in 96 % tions and digital payments . or more generally . the electronic commerce ove r of the cases where the crackers got in, they went undetected . The best metho d the insecure Internet/World Wide Web . For example . if Bob wants to orde r of protection for a local network system is to encrypt all the informatio n a book from Alice's bookshop (see Figure 3 .16), he uses the secure tunnel t o stored in the local system and to decrypt it whenever an authorized use r send Alice his credit card number : on receiving Bob's credit card number .. wants to use the information . This method has an an important applicatio n Alice sends Bob the required book . It is worthwhile pointing out that a grea t in secure communications – to encrypt the data leaving the local network an d deal of effort has been put into commercial cryptographic-based Internet/We b then to decrypt it on the remote site ; only friendly sites will have the require d security in recent years . Generally speaking . there are two categories of com- encryption/decryption key to receive or to send data, and only the router s mercial cryptographic systems used for securing the Internet/Web communi- which connect to the Internet require to encrypt/decrypt . This technique is cations . The first group are programs and protocols that are used for encryp- known as the cryptographic tunnels (see Figure 3 .15), which has the extra tion of e-mail messages . These programs take a plaintext message, encryp t advantage 1 hat data cannot be easily tapped-into (Buchanan [42]) . A further it and either store the encrypted message on a local machine or transmit it

3 . Applied Number Theory in Computing/Cry ptography 3 .3 Cryptography and Information Security 40 7 406 Ciphertext for \"Mv credit card numbe s . . . In me Alice's Booksho p Task Force (IETF) is in the process of creating a Transport Secure Laye r (TSL) to merge the SSL and PCT . Bo b (Encryption/Decryptio n Key ) (3) Secure HyperText Transport Protocol (S-HTTP) : S-HTTP is developed (Encryption/Decryptio n by Enterprise Integration Technologies (EIT) . It uses a. modified versio n Key of HTTP clients and the server to allow negotiation of privacy, authen- tication and integrity characteristics . Ciphretcxt for \"Your b,6ok was mailed to yo u (4) Secure Transaction Technology Protocol (STT) : STT is a standard devel- Eavesdropper Ev e oped jointly by Microsoft and Visa International to enable secure credi t \"What did they say??? \" card payment and authorisation over the web . Figure 3 .16 . Electronic book ordering (5) Secure Electronic Payment Protocol (SEPP) : SEPP is another electroni c payments scheme, sponsored by MasterCard and developed in associa- to another user over the Internet . Some popular systems that fall into thi s tion with IBM, Netscape, CyberCash and GTE . Both STT and SEP P category include the following : have been superseded by SET (Secure Electronic Transactions) . proposed jointly by MasterCard and Visa . (1) Pretty Good Privacy (PGP) : PGP is a program created by Philip Zim- mermann to encrypt e-mails using public-key cryptography. PGP was Exercise 3 .3 .14 . Try to order a. copy of a book, e .g ., the present book, fro m electronically published as free software in 1991 . It has now become th e Springer-Verlag by using your SSL-aware web browser to create an encrypte d worldwide de facto standard for e-mail encryption . connection to the Springer-Verlag web server : (2) Secure/Multipurpose Internet Mail Extensions (S/MIME) : S/MIME i s https ://www .springer .d e a security enhancement to the MIME Internet e-mail format standard . based on technology from RSA Data, Security . Although both PGP an d Now we are in a position to discuss a real-world commercial cryptographi c S/MIME are on an IETF (Internet Engineering Task Force) standard s protocol, the SET protocol for secure credit card payment over the insecur e track, it appears likely that S/MIME will emerge as the industry standard Internet . It is a simplified version of the SET, based on a description give n for commercial and organizational use . while PGP will remain the choic e in [87) . for personal e-mail security for niany users . Algorithm 3 .3 .10 (SET protocol) . This algorithm describes a crypto- The second category of cryptographic systems are network protocols used fo r graphic protocol for credit card payment over the Internet . Suppose that Alic e providing confidentiality . authentication . integrity. and nonrepudiation in a wants to purchase a book from Bob (an Internet bookshop) using the credi t networked environment . These systems require real-time interplay between a card issued by Lisa (a bank), but Alice does not want Bob to see her credit car d client and a server to work properly . Listed below are some systems fallin g number, however she wants Bob to send her the book and Lisa to send Bo b into this category : the payment . And of course, Alice also wants that the communications betwee n Bob, Lisa and herself is kept confidential even if someone is eavesdropping ove r (1) Secure Sockets Layer protocol (SSL) : SSL is developed by Netscap e the Internet . Communications . and supported by Netscape and Microsoft browsers . I t provides a secure channel between client and server which ensures privacy [11 Alice first prepares two documents : a purchase order O stating she want s of data, authentication of the session partners and message integrity . to order a book from Bob, and a payment slip P, providing Lisa the car d (2) Private Communication Technology protocol (PCT) : PCT, proposed by Microsoft, is a slightly modified version of SSL . The Internet Engineering number to be used in the transaction, and the amount to be charged . The n she computes the digests : o = H(0 ) (3 .120) p = H(P ) and produces a digital signature S for the digest of the concatenation of o and p : S = P.a( H ( o II p)) = r(H H (H ( 0 ) II H ( P))) (3 .121 )

3 . Applied Number Theory in Computing/Cryptography 3 .3 Cryptography and Information Seen 40 9 408 where D,t is the function used by Alice to sign, based on her private key . 3 .3 .14 Steganography Alice encrypts the concatenation of o, P and S with Lisa's public key, whic h Cryptography means `\"secret writing A closely related area to cryptograph y is steganography, which literally means covered writing as derived from Greek yields the ciphertext : and deals with the hiding of messages so that the potential monitors do not even know that a message is being sent . It is different from cryptography CL=EL(oII P 11 S) . (3 .122 ) where they know that a secret message is being sent . Figure 3 .17 shows a schematic diagram of a typical steganography system . Generally, the sender She also encrypts with Bob's public key the concatenation of 0, p and S and gets the ciphertext : Public and Insecure Channel Stegoanalys t CB = EB (O 11 p II S) . (3 .123 ) She then sends CL and CB to Bob . [2] Bob retrieves 0, p and S by decrypting CB with his private key . He verifie s the authenticity of the purchase order 0 with Alice's public key by checkin g that Stego-key Stego-ke y Ea(S) = H(H(O p)) (3 .124 ) and forwards C L to Lisa . Message Message Concealing Extracting [3] Lisa retrieves o, P and S by decrypting C L with private key. She verifies th e authenticity of the payment slip P with Alice's public key by checking tha t Stego-Message 4( ) =E S H ( o II H ( P)) (3 .125 ) and verifies that P indicates a payment to Bob . She then creates an au- Embedded-Message Embedded Message thorization message Ill that consists of a transaction number, Alice's name , (secret) (secret ) and the amount she agreed to pay . Lisa computes the signature T of Al , Cover-messag e encrypts the pair (AI,T) with Bob's public key to get the ciphertext : Cover-message (non-secret ) (non-secret ) C AI = Et3(M T) (3 .126 ) Figure 3 .17 . A steganographic system and sends it to Bob . performs the following operations : [4] Bob retrieves Al and T by decrypting C t1. and verifies the authenticity o f (1) write a non-secret cover-message, the authorization message Ill with Lisa's public key, by checking tha t (2) produce a stego-message by concealing a secret embedded message o n EL (T) ll . (3 .127 ) the cover message by using a stego-key , He verifies that the name in AI is Alice's, and that the amount is the cor- (3) send the stego-message over the insecure channel to the receiver . rect price of the book . He fulfills the order by sending the book to Alice and requests the payment from Lisa by sending her the transaction numbe r At the other end . on receiving the stego-message, the intended receiver ex - encrypted with Lisa's public key. tracts the secret embedded message from the stego-message by using a pre - agreed stego-key (often the same key as used in the message concealing) . [5] Lisa pays Bob and charges Alice's credit card account . Historical tricks include invisible inks . tiny pin punctures on selected char- acters . minute differences between handwritten characters, etc . For example . Kahn tells of a classical Chinese practice of embedding a code ideogram a t a prearranged place in a dispatch (Kahn [117]) . More recently, people have hidden secret messages in graphic images by replacing the least significan t bits of the image with a secret message (Schneier [218]) .

3 . Applied Number Theory in Computing/Cryptography 3 .4 Bibliographic Notes and Further Reading 41 1 410 Note that the procedures of message concealing and message extractin g + + xx+ xxx+ in steganography are more or less the same as the message encryption an d [3] Bob records the result of his measurements but keeps it secret : message decryption in cryptography. It is this reason that steganography is often used together with cryptography . For example, an encrypted messag e [4] Bob publicly announces the type of measurements he made . and Alic e may be written using invisible ink . Note also that a steganographic syste m tells him which measurements were of correct type : can either be secret or public . In a public key steganographic system . differen t keys are used for message concealing and message extracting . Readers inter- ested in steganography are suggested to consult the workshop proceedings o n Information Hiding (Anderson [9] and Aucsmith [13]) . 3 .3 .15 Quantum Cryptography [5] Alice and Bob keep all cases in which Bob measured the correct type . These cases are then translated into hits {0,1} and thereby become the key: t -4 / t In Chapter 2 . we introduced some quantum algorithms for factoring larg e 10 0 integers and computing discrete logarithms . It is evident that. if a quantu m computer is available, then all the public key cryptographic systems based o n [6] Using this secret key formed by the quantum channel . Bob and Alice can the difficulty of integer factorization and discrete logarithms will he insecure . now encrypt and send their ordinary messages via the classic public-key However, the cryptographic systems based on quantum mechanics will stil l channel . be secure even if a quantum computer is available . To make this hook a s complete as possible . we shall introduce in this subsection some basic idea s An eavesdropper is free to try to measure the photons in the quantu m of quantum cryptography . More specifically, we shall introduce a quantu m channel, but, according to the law of quantum mechanics, he cannot in general analog of the Diffie-Hellman key exchange/distribution system, proposed b y do this without disturbing them, and hence, the key formed by the quantu m Bennett and Brassard in 1984 . channel is secure . First let us define four polarizations as follows : {0° . 45°, 90° . 135°} `ref T, I . (3 .128 ) 3 .4 Bibliographic Notes and Further Reading The quantum system consists of a . transmitter, a receiver, and a quantu m We interpret applied number theory in this book as the application of num- ber theory to computing and information technology, and thus this chapte r channel through which polarized photons can be sent [25] . By the law of is mainly concerned with these applications of number theory . Even with thi s restriction, we argue that it is impossible to discuss all the computing relate d quantum mechanics, the receiver can either distinguish between the rectilin- applications of number theory in a single book . We have, in fact only dis- cussed the applications of number theory to the design of computer system s ear polarizations {-s, or reconfigure to discriminate between the diagona l and cryptosystems . but in any case, he cannot distinguish both types . polarizations {/, v}. Our first application of nnmiber theory in computing is the design of com - puter systems : these include residue number systems and residue computers . The system works in the following way : complementary arithmetic and fast adders, error detections and corrections . the construction of hash functions (particularly minimal perfect hash func- [1] Alice uses the transmitter to send Bob a sequence of (p/h,otTon.s.Nea}c. hFoofr tions) . and the generation of random numbers/bits . Our- aim was to show them should be in one of the four polarizations {—z, the applicability of number theory in computer systems design rather than the actual design of the computer (hardware or software) systems . There are instance . Alice could choose . at random . the following photon s to be sent to Bob . [2] Bob then uses the receiver to measure the polarizations . For each pho- ton received from :Vice . Bob chooses, at random, the following type o f measurements {+, x} :

3 . Applied Number Theory in Computing/Cryptography 3 .4 Bibliographic Notes and Further Reading 41 3 412 plenty of books available on computer arithmetic (including residue numbe r [3] A . D . Rubin and D . E . Geer Jr . \"A Survey on Web Security . pp 34-42 . systems and complementary arithmetic) and fast computer architectures, bu t those by Koren [132], McClellan and Radar [149] . Soderstrand et al . [243] , [4] R . Oppliger, \" Security at the Internet Layer \" , pp 43-47 . and Szabo and Tanaka [247] are highly recommended . A standard referenc e that contains many applications of number theory in computer arithmetic . [5]W . A . Arbaugh . et al ., \"Security for Virtual Private Intranets\" . pp 48 -56 . random number generation and hash functions (and many more) is Knuth' s three volumes of The Art of Computer Programming [122], [123], and [124] . [6] T . D . Tarman, et al . . \"Algorithm-Agile Encryption in ATM Networks\" . For error detection and correction codes, see . for example, Gallian [77] . Hil l PP 57 64 . [104], and Welsh [252] . Note that the paper by Rubin and Geer [213] also discussed some interestin g Cryptography, particularly public-key cryptography, is an area that heav- issues in mobile code security . All the above mentioned papers are easy to ily depends on ideas and methods from number theory ; of course, number the- read and hence suitable for beginners in the field . ory is also useful in information systems security, including communicatio n network security . In this chapter . we have provided a mathematical foun- As by-products to cryptography, we have also introduced some basic con- dation for cryptography and information security . Those who desire a more cepts of steganography and quantum cryptography. There has been an in- detailed exposition in the field are invited to consult Bauer [20], Koblit z creasing number of references in these two fields in recent years ; intereste d [128] and [129] . and Pinch [184] ; for elliptic curve public-key cryptography , readers are referred to . for example, Anderson [9], Aucsmith [13] . Hughes see Menezes [155] . Readers may also find the following books useful in cryp- [106], Inamori [110] and Lo [146] . and the references therein . tography and computer security : Jackson [112], Kaufman et al . [118], Pfleeger [182], Salomaa [215], Smith [242], Stinson [246] and Welsh [252] . The book s In addition to computing and cryptography, number theory has also bee n edited by Pomerance [190] and [44] contain a number of excellent surve y successfully applied to many other areas such as physics, chemistry . acous- papers on cryptology and random number generation . tics, biology, engineering, dynamical systems . digital communications, digita l signal processing, graphics design, self-similarity, and even music . For more The series of conferences proceedings entitled Advances in Cryptology information about these applications, readers are invited to consult Burr [44] , published in Lecture Notes in Computer Science by Springer-Verlag is a n Schroeder [222] and Waldschmidt, Moussa, Luck and Itzykson [250] . important source for new developments in cryptography and information se- curity. There is a special section on computer and network security in the Scien- tific American, 279, 4(1998), 69 89 ; it contains the following articles : [1] C . P . Meinel . \"How Hackers Break in . . . and How They Are Caught\" . pp 70-77 . [2] \"How Computer Security Works\" , [i] W . Cheswick and S . M . Bellovin. \"Firewalls\", pp 78-79 . [ii] W. Ford, \"Digital Certificates\", page 80 . [iii] J . Gosling, \"The Java Sandbox\" . page 81 . [3] P . R . Zimmermann, \"Cryptography for the Internet\", pp 82-87 . [4] R . L . Rivest . \"The Case Against Regulating Encryption Technolog ,P P 88 89 . An issue of the IEEE journal Computer, 31 . 9(1998) . also has a special report on computer and network security . which contains the following six papers : [1] P . W . Dowd and J . T . McHenry . \" Network Security : It ' s Time to Take It Seriously \" . pp 24- 28 . [2] B . Schneier, \" Cryptographic Design Vulnerabilities \" , pp 29-33 .

Bibliography 1. L . M . Adleman, \"A Subexponential Algorithmic for the Discrete Logarith m Problem with Applications to Cryptography\", Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, 1979, 5 5 60 . 2. L . M . Adleman, \"Algorithmic Number Theory The Complexity Contribution\" , Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, 1994 . 88-113 . 3. L . M . Adleman, C . Pomerance, and R . S. Rumely. \"On Distinguishing Prim e Numbers from Composite Numbers\" . Annals of Mathematics . 117 (1983), 17 3 206 . 4. L . M . Adleman and M . D . A . Huang . Primality Testing and Abelian Varieties over Finite Fields . Lecture Notes in Mathematics 1512, Springer-Verlag, 1992 . 5. A . V. Aho, J . E . Hoperoft and J . D . Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974 . 6. W . Alford . G . Granville and C . Pomerance, \"There Are Infinitely Man y Carmichael Numbers\" . Annals of Mathematics, 140 (1994), 703-722 . 7. R Alter, \" Computations and Generalizations of a Remark of Ramanujan\" , Analytic Number Theory. Proceedings, Lecture Notes in Mathematics 899 . Springer-Verlag, 1981 . 183-196 . 8. J . A . Anderson and J . M . Bell, Number Theory with Applications . Prentice - Hall, 1997 . 9. R . Anderson (editor) . Information Hiding, First International Workshop ; Pro- ceedings . Lecture Notes in Computer Science 1174 . Springer-Verlag, 1996. 10. G . E . Andrews . Number Theory . W . B . Sayders Company, 1971 . Also Dover Publications . 1994 . 11 T . M. Apostol, Introduction to Analytic Number Theory, Corrected 5th Print- ing, Undergraduate Texts in Mathematics, Springer-Verlag . 1998 . 12 A . O . L . Atkin and F . Morain . \" Elliptic Curves and Primaiity Proving\", Math- ematics of Computation. 61 (1993), 29 68 . 13. D . Aucsmith (editor), Information Hiding, Second International Workshop , Proceedings . Lecture Notes in Computer Science 1525 . Springer-Verlag . 1998 . 14. E . Bach . M . Giesbrecht and J . McInnes, The Complexity of Number Theoret- ical Algorithms. Technical Report 247/91 . Department of Computer Science . University of Toronto . 1991 . 15. E . Bach . G . Miller and J . Shallit, \"Sums of Divisors . Perfect Numbers and Factoring\" , SIAM Journal on Computing, 15 (1989), 1143 1154 .

Bibliography Bibliography 11 7 416 16. E . Bach and J . Shallit, Algorithmic Number Theory I Efficient Algorithms . 36. R . P . Brent, \"Some Integer Factorization Algorithms using Elliptic Curves\" . MIT Press, 1996 . Australian Computer Science Comm unications. 8 (1986), 149-163 . 37. R . P. Brent, \"Primality Testing and Integer Factorization\", Proceedings of_lus- 17. A . Backer, A Concise Introduction to the Theory of Numbers . Cambridge Uni- tralian Academy of Science CAannnbuearrlaG. 1e9n9e1ra.l14M2e6et.ing versity Press . 1984 . of Mathematics in Science . Symposium on the Rol e 18. R . J . Baillie and S . S . Wagstaff. Jr . . \"Lucas Pseudoprimeti\" . Mathematics of 38. R . P. Brent, \"Uses of Randomness in Com putation, Report TR-CS-94-06 . Computation . 35 (1980) . 13911417 . Computer Sciences Laboratory, Australian National University, 1994. 19. S . Battiato and W . Borho . \"Bleeding Amicable Numbers in Abundance II \" , 39. R . P. Brent, G . L . Cohen and H . J . .I to Riele . Improved Techniques for Lowe r Mathematics of Computation . 70 (2001), 1329-1333 . Bounds for Odd Perfect Numbers\", Mathematics of Computation, 57 (1991) . 857 868 . 20. F . L . Bauer, Decrypted Secrets Methods and Maxims of Ciyptology, 2n d Edition, Springer-Verlag . 2000 . 40. D . M . Bressoud, Factorization and Prirnalitr Testing, Undergraduate Texts i n Mathematics, Springer-Verlag, 1989 . 21. B . Beckett, Introduction to Crvptology and PC Security, McGraw-Hill, 1997 . 22. M . Bellare and P. Gogaway, \" Optimal Asymmetric Encryption\" . Advances in 41. E . F . Brickell, D . M . Gordon and K . S . McCurley, \" Fast Exponentiation wit h Precomputation\" (Extended Abstract), Advances in Cryptography, EURO- Cryptography, CRYPTO '94, Proceedings . Lecture Notes in Computer Science CRYPT '92, Proceedings, Lecture Notes in Computer Science 658, Springer- 950 . Springer-Verlag, 1995, 92111 . Verlag, 1992, 200-207 . 23. P . Benioff, `\"The Computer as a Physical System A Microscopic Quantu m 42. W . Buchanan, Mastering the Internet . Macmillan, 1997 . Mechanical Hamiltonian Model of Computers as Represented by Turing Ma- 43. J . P. Buhler (editor), Algorithmic Number Theory . Third International Sym- chines\", Journal of Statistical Physics, 22 (1980), 563-591 . posium, ANTS-III, Proceedings, Lecture Notes in Computer Science 1423 , 24. C . H . Bennett, \"Quantum Information and Computation\" . Physics Today, Oc- Springer-Verlag, 1998 . tober 1995, 24-30 . 44. S . A . Burr (editor), The Unreasonable Effectiveness of Number Theory, Pro- 25. C . H . Bennett . G . Brassard and A . K . Ekert, \"Quantum Cryptography\", Sci- ceedings of Symposia in Applied Mathematics 46, American Mathematical So- entific American, October 1992, 26 33 . ciety, 1992 . 26. C . H . Bennett, \" Strengths and Weakness of Quantum Computing\", SIAM Jour- 45. CACM . \"The Digital Signature Standard Proposed by NIST and Responses t o nal on Computing, 26 (5)1997, 1510 1523 . NIST's Proposal\", Communications of the ACM. 35, 7(1992), 36 54 . 27. E . Bernstein and U . Vazirani, \" Quantum Complexity Theory\", SIAM Journal 46. J . R. Chen, \"On the Representation of a Large Even Integer as the Sum of a on Computing, 26 5(1997), 14111473 . Prime and the Product of at most Two Primes\" . Scientia Sinica, XVI, 2(1973) , 157-176 . 28. M . Blinn and S . Goldwasser, \"An Efficient Probabilistic Public-key Encryp- tion Scheme that Hides all Partial Information\", Advances in Cryptography. 47. K . Chen . \" Authenticated Encryption Scheme Based on Quadratic Residue\" , CRYPTO ' 84, Proceedings, Lecture Notes in Computer Science 196, Springer- Electronics Letters, 34, 22(1998), 2115-2116 . Verlag 1985, 289 302 . Boll :1986 B . Bollobds (editor) . Littlewood's Miscellany, Cambridge Universit y 48. S . S . Coern. \"Mathematics in the 21st Century\" . Advances in Mathematics Press, 1986 . (China), 21, 4(1992), 385-387 . 29. E . Bombieri, Problems of the Millennium : The Riemann Hypothesis . Institut e 49. L . Childs, A Concrete Introduction to Higher Algebra, Undergraduate Text s for Advanced Study . Princeton, 2000 . in Mathematics . Springer-Verlag, 1979 . 30. D . Boneh . \"Twenty Years of Attacks on the RSA Cryptos}stem' . Notices of 50. H . Cohen . A Course in Computational Algebraic Number Theory, Graduat e the AMTS . 46 2(1999), 203-213 . Texts in Mathematics 138, Springer-Verlag . 1993 . 31. NV . Borho, \" Uber die Fixpunkte der k-fach iterierten Teilersummenfunktio n 51. J . H . Conway and R . K . Guy. The Book of Numbers. Springer-Verlag, 1996 . Mitt . Math . Gesellsch . Hamburg, 9 5(1969) . 34 48 . 52. S . Cook . The P versus NP Problem, University of Toronto . April, 2000 . 32. NV . Borho and H . Hoffmann, \"Breeding Amicable Numbers in Abundance' . (Manuscript prepared for the Clay Mathematics Institute for the Millenniu m Mathematics of Computation, 46 (1986), 281-293 . Prize Problems ; revised in November 2000 . ) 53. J . W . Cooley and J . \\V . Tukey, \"An Algorithm for the ALachine Calculation o f 33. G . Brassard, \"A Quantum Jump in Computer Science\", Computer Science Complex Fourier Series\" , Mathematics of Computation . 19 (1965), 297301 . Today Recent Trends and Development . Lecture Notes in Computer Scienc e .54 . 'F . H . Cormen_ C . E . Ceiserson and R . L . Rivest . Introduction to Algorithms . 1000, Springer-Verlag, 1995 . 1-14. MIT Press, 1990 . 34. R . P . Brent, \" Irregularities in the Distribution of Primes and Twin Prunes \" . 55. R . Crandall, J . Doenias, C . Norrie and J . Young . \" The Twenty-Second Ferma t Mathematics of Computation . 29 (1975) . 43 56 . Number is Composite \" , Mathematics of Computation, 64 (1995) . 863 869 . 35. R . P . Brent, \" An Improved Monte Carlo Factorization Algorithm BIT, 20 56. R . Crandall and C . Pomerance . Prime Numbers A Computational Perspec- (1980), 176-184 . tive, Springer-Verlag, 2001 .

Bibliograpl Bibliography 418 57. I . Damgard (editor), Lectures in Data Security . Lecture Notes in Computer 78. M . Gardner, `\"Mathematical Games A New Kind of Cipher that Would Talc,. Science 1561 . Springer-Verlag . 1999 . Millions of Years to Break\" . Scientific American, 237 . 2(1977) . 120 124 . 79. M. 58. H . Davenport, The Higher Arithmetic . 7th Edition, Cambridge University the R . Garen and D . S . Johnson, Computers and Intractability A Guide to Press . 1999 . Theory of NP-Completeness . W . H . Freeman and Company . 1979 . 59. M. Deleglise and J . Rivat . \"Computing ir(r) the Meissel . Lehmer, Lagarias , 80. S . Garfinkel, Web Security and Commerce, O ' Reilly . 1997 . Miller . Odlvzko Method\" . Mathematics of Computation . 65 (1996) . 235-245 . 81. P . Garrett . Making . Breaking Codes : An Introduction to Cryptology . Prentice- 60. D . C . Denson, The Moment of Proof Mathematical Epiphanies, Oxford Uni- Hall, 2001 . versity Press, 1997 . 82. C . F . Gauss, Disquisitiones Arithmeticae . G . Fleischer, Leipzig, 1801 . Englis h 61. J . M . Deshouillers . G . Effinger, H . J . J . te Riele and D . Zinoviev. \"A Complet e translation by A . A . Clarke, Yale University Press, 1966 . Revised English trans- Vinogradov 3-Prime Theorem under the Riemann Hypothesis\" . Electronic Re - lation by W. C . Waterhouse, Springer-Verlag, 1975 . search Announcements of the AMS, 3 (1997), 99-104 . 83. P. Giblin, Primes and Programming - An Introduction to Number Theory with 62. J . M . Deshouillers, H . ,4 . .I . to Riele and Y. Saouter, New Experimental Results Computing, Cambridge University Press . 1993 . Concerning the Goldbach Conjecture . Technical Report M-1AS-R.9804, Centre for Mathematics and Computer Science (CWI), Amsterdam, 1998 . 84. S . Goldwasser, \"The Search for Provably Secure Cryptosystems\", Cryptology and Computational Number Theory, edited by C . Pomerance, Proceedings o f 63. D . Deutsch, \"Quantum Theory, the Church—Turing Principle and the Universa l Symposia in Applied Mathematics 42, American Mathematical Society, 1990 . Quantum Computer\" . Proceedings of the Royal Society of London, Series A . 85. S . Goldwasser 400 (1985), 96 117 . Proceedings of and J . Kilian . \"Almost All Primes Can be Quickly Certified\" , 1986, 316-329 . the 18th ACM Symposium on Theory of Computing . Berkeley. 64. K . Devlin . Mathematics : The Science of Patterns, Scientific American Library , 1997 . 86. S . Goldwasser and J . Kilian . \" Primality Testing Using Elliptic Curves\", Journa l of ACM. 46, 4(1999), 450-472 . 65. L . E. Dickson, History of the Theory- of Numbers I Divisibility and Primality , G . E. Stechert Sr:. Co ., New York, 1934 . 87 M . T . Goodrich and R. Tamassia, Algorithm Design : Foundations . Analysis . and Internet Examples . John Wiley & Sons. 2001 . 66. W . Diffie and E . Hellman, \"New Directions in Cryptography\" . IEEE Transac- tions on Information Theory, 22, 5(1976), 644-654 . 88. S . Goldwasser and S . Micah, 'Probabilistic Encryption\", Journal of Computer and System Sciences, 28 (1984) . 270 299 . 67. W . Diffie and E . Hellman, \" Privacy and Authentication: An Introduction t o Cryptography\", Proceedings of the IEEE, 67, 3(1979), 393 427 . 89. D . M . Gordon and K. S . McCurle \"Massively Parallel Computation of Dis- crete Logarithms\" . Advances in Cryptography. Crypto '92, Proceedings, Lec- 68. P . G . L . Dirichlet, Lecturers on Number Theory.-. Supplements by R . Dedekind , ture Notes in Computer Science 740, Springer Verlag, 1992, 312 323 . American Mathematics Society and London Mathematics Society, 1999 . 90. D . M . Gordon, \"Discrete Logarithms in GF(p) using the Number Field Sieve\" . 69. T . ElGama1, \"A Public Key Crvptos}stem and a . Signature Scheme based on SIAM Journal on Discrete Mathematics, 6, 1(1993), 124-138 . Discrete Logarithms\", IEEE Transactions on Information Theory, 31 (1985) , 496-472 . 91. F . T . Grampp and R . H . Morris, \"UNIX Operating System Security\" . AT& T Bell Laboratories Technical Journal, 63 (1984), 1649 1672 . 70. G . Ellis, Rings and Fields . Oxford University Press, 1992 . 92. A . Granville, J . van de Lune and H . J . J . te Riele, `\"Checking the Goldbach 71. S . S . Epp . Discrete Mathematics with Applications . 2nd Edition, PWS Pub- Conjecture on a Vector Computer\", Number Theory and Applications . edite d lishing Company. Boston . 1995 . by R . A . Mollin, Kluwer Academic Publishers . 1989 . 423-433 . 72. Euclid, The Thirteen Books of Euclid's Elements, Translated by T . L . Heath . 93. D . Cries and F . B . Schneider, A Logical Approach to Discrete Math . Texts an d Great Books of the TT estern World 11 . edited by R . M . Hutchins, Willia m Monographs in Computer Science, Springer-Verlag. 1993 . Benton Publishers . 1952 . 94. R. . K . Guy, Unsolved Problems in Number Theory. 2nd Edition .. Springer- 73. Euclid . The Thirteen Books of Euclid's Elements . Second Edition . Translate d Verlag, 1994 . by Thomas L . Heath . Dover Publications, 1956 . 95. D . Guedj, Numbers The Universal Language . Thames and Hudson . 1997 . 74. R . P . Fev< rmran . \" Simulating Physics with Computers'' . International Journal 96. F . Guterl, \" Suddenly. Number Theory Makes Sense to Industry\" . International of Theoretical Physics . 21 (1982) . 467-488 . Business Week, 20 June 1994, pp . 62-64 . 75. R. P . Fevnman . Fevnman Lectures on Computation . Edited by A . .I . G . Hey and R . W . Allen . Addison-Wesley. 1996 . 97. H . Halberstam and H . E . Richert, Sieve Methods . Academic Press . 1974 . 98. G . H . Hardy. A Mathematician 's Apology-, Cambridge University Press . 1979 . 76. J . B . Fraleigh, .A First Course in Abstract algebra ; 5th Edition . Addison- Wesley. 1994 . 99. G . H . Hardy and J .E . Littlewood . \" Some Problems of ' Partitio Numerorum ' . III : On the Express of a Number as a Sum of Primes \", _lcta lathematica . 44 77. J . A . Gallian, \" Error Detection Methods\" . ACM Computing- Surveys, 28 , (1923), 1- 70 . 3(1996) . 503-517 .

Bibliography Bibliography 42 1 420 100. G . H . Hardy and E . M . Wright, An Introduction to Theory of Numbers, 5t h 124. D . E . Knuth . The Art of Computer Programming III Sorting and Searching, Edition, Oxford University Press . 1979 . 2nd Edition, Addison-Wesley. 1998 . 101. D . R . Heath-Brown, \"Odd Perfect Numbers\" . Mathematical Proceedings of 125. C . Ko and Q . Sun . Lecture Notes in Number Theory (In Chinese), Highe r Cambridge Philosophy Society, 115, 1(1994), 191-196 . Education Press; Beijing . 1984 . 102. A . Heck, Introduction to Maple, 2nd Edition, Springer-Verlag, 1996 . 126. N . Koblitz, \"Elliptic Curve Cryptography\" . Mathematics of Computation ; 4 8 (1987) . 203-209 . 103. I. N. Herstein, Topics in Algebra, 2nd Edition. Wiley. 1975 . 104. R . Hill . A First Course in Coding Theory. Oxford University Press, 1991 . 127. N . Koblitz, Introduction to Elliptic Curves and Modular Forms, 2nd Edition . 105. L . Hua . Introduction to Number Theory. English Translation from Chinese Graduate Texts in Mathematics 97, Springer-Verlag. 1993 . by P. Shiu, Springer-Verlag, 1980 . 128. N . Koblitz . A Course in Number Theory and Cryptography, 2nd Edition . Graduate Texts in Mathematics 114 . Springer-Verlag . 1994 . 106 . R. J . Hughes, \"Cryptography, Quantum Computation and Trapped Ions\" , Philosophic Transactions of the Royal Society London . Series A, 356 (1998) . 129 . N . Koblitz, Algebraic Aspects of Cryptography, Algorithms and Computatio n 1853 1868 . n Mathematics 3, Springer-Verlag, 1998 . 107 . R . M . Huizing. An Implementation of the Number Field Sieve. Note NM - 130 . N . Koblitz . Cryptography, in : Mathematics Unlimited — 2001 and Be- R9511, Centre for Mathematics and Computer Science (CWI), Amsterdam , yond, Edited by B . Enguist and W . Schmid . Springer-Verlag, 2001 . 749- 769 . 1995 . 131. S . Koncagin and C . Pomerance, \"On Primes Recognizable in Deterministi c 108. T . W . Hungerford, Abstract Algebra An Introduction. Saunders College Polynomial Time\", The Mathematics of Paul Erdds, edited by R . L . Graham Publishing, 1990 . and J . Nesetril, Algorithms and Combinatorias 1.3, Springer-Verlag, 1997, 17 6 198 . 109. D . Husemoller, Elliptic Curves, Graduate Texts in Mathematics 111, Springer - Verlag, 1987 . 132. I . Koren . Computer Arithmetic Algorithms, Prentice-Hall, 1993 . 110. H . Inamori . A Minimal Introduction to Quantum Key Distribution, Centr e 133. H . Krishna . B . Krishna, K . Y. Lin, and J . D . Sun . Computational Number for Quantum Computation, Clarendon Laboratory, Oxford University, 1999 . Theory and Digital Signal Processing, CRC Press, 1994 . 111. K . Ireland and M . Rosen, A Classical Introduction to Modern Number Theory, 134. E . Kranakis . Primality and Cryptography, John Wiley & Sons, 1986 . 2nd Edition . Graduate Texts in Mathematics 84 . Springer-Verlag, 1990 . 135. R . Kumanduri and C . Ronero, Number Theory with Computer Applications. 112. T . H . Jackson, From Number Theory to Secret Codes, A Computer Illustrated Prentice-Hall, 1998 . Text, Adam Hilger . Bristol, 1987 . 136. J . C . Lagarias, \"Pseudorandom Number Generators \" , Cryptology and Com- 113. G . Jaeschke, \"Reciprocal Hashing : A Method for Generating Minimal Perfec t putational Number Theory, edited by C . Pomerance, Proceedings of Symposi a Hashing Functions\" , Communications of the ACM, 24, 12(1981), 829-833 . in Applied Mathematics 42, American Mathematical Society, 1990, pp 115 143 . 114. D . S . Johnson . \"A Catalog of Complexity Classes \" . Handbook of Theoretical 137. S . Lang, Elliptic Functions, 2nd Edition, Springer-Verlag . 1987 . Computer Science, edited by J . van Leeuwen . MIT Press . 1990 . 69-161 . 138. J . can Leeuwen (editor), Handbook of Theoretical Computer Science . MI T 115. R . Jozsa, \"Quantum Factoring, Discrete Logarithms, and the Hidden Sub - Press, 1990 . group Problem\" . Computing in Science and Engineering, March/April 2001 , 139. R . S . Lehman . \"Factoring Large Integers\" . Mathematics of Computation, 2 8 34 43 . (1974) . pp 637-646 . 116. B . S . Kaliski . \"A Pseudo-Random Bit Generator Based on Elliptic Curv e Logarithms \" . Advances in Cryptography. CRYPTO ' 86 . Proceedings, Lectur e 140. H . W . Lenstra . Jr ., \"Factoring Integers with Elliptic Curves\" , Annals of Math- Notes in Computer Science 263, Springer-Verlag, 1986, 84103 . ematics . 126 (1987), 649-673 . 1.17. D . Kahn . The Codebreakers . Macmillan . 1967 . 141. A . K . Lenstra and H . W . Lenstra, Jr . . The Development of the Number Field 118. C . Kaufman . R . Perlman and M . Speciner . Network Security - Private Com- Sieve. Lecture Notes in Mathematics 1554. Springer Verlag, 1993 . munication in a Public World . Prentice-Hall . 1995 . 142. H . R . Lewis and C . H . Papadimitriou . Elements of the Theory of Computation , 119. A. Ya . Khinchin . Continued Fractions. English translation from Russian . 2nd Edition . Prentice-Hall . 1998 . Chicago University Press, 1964 . 143 . P . Linz, An Introduction to Formal Languages and Automata . 2nd Edi on . 120. J . Kilian . Uses of Randomness in Algorithms and Protocols . MIT Press . 1990 . Jones and Bartlett Publishers . 1997 . 121. D . E . Knuth . \" Computer Science and its Relation to Mathematics\" . American 144 . .1 . E . Littlewood, A Mathematician's Miscellany. Methuen & Co . Ltd . London ; Mathematical Monthly. 81, 4(1974), 323 343 . 1953 . (This book later became Littlewood's Miscellany . edited by B . Bollobas 122. D . E . Knuth, The Art of Computer Programming I Fundamental Algorithms . and published by Cambridge University Press in 1986 . ) 3rd Edition . Addison Wesley, 1997. 145. C L . Liu . Introduction to Combinatorial Mathematics, McGraw-Hill, 1968 . 123. D . E . Knuth, The Art of Computer Programming II Seminumerical Algo- 146. H . K . Lo . \" Quantum Cryptography\" , Introduction to Quantum Computatio n ritlmrs, 3rd Edition, Addison-Wesley. 1998 . and Information . edited by H . K . Lo, S . Popescu and T . Spiller. World Scientific . 1998 . 76 119 .

Bibliography Bibliography 42 3 422 147. J . van de Lune, H . J . J . to Riche and D . T . Winter . \"On the Zeros of th e 168. F . Morain . Courbes Elhptiques et Tests de Pr'imalite, Universite Claud e Riemann Zata Function in the Critical Strip IV\" . Mathematics of Computation , Bernard . Lyon I . 1990 . 46 (1986) . 667 681 . 169. M. A . Morrison and J . Brillhart . -A Method of Factoring and the Factorizatio n 148. R . S . Macgregor . A . Aresi and A . Siegert, WW W'.Security How to Build a of F,\" . Mathematics of Computation, 29 (1975) . 183 205 . Secure World Wide Web Connection . Prentice-Hall, 1996 . 170. R . Mottvani and P . Raghavan . Randomized Algorithms. Cambridge Universit y 149. J . H . McClellan and C . M . Radar, Number Theory in Digital Signal Process- Press, 1995 . ing, Prentice-Hall, 1979 . 171. C . J . Mozzochi, \"A Simple Proof of the Chinese Remainder Theorem\" . Amer- 150. K . S . McCurley. \"The Discrete Logarithm Problem\" . Cryptology and Com- ican Mathematical Monthly. 74 (1967) . 998 . putational Number Theory, edited by C . Pomerance, Proceedings of Symposi a in Applied Mathematics 42 . American Mathematics Society. 1990 . pp 49 74 . 172. M . B . Nathanson, Elementally Methods in Number Theoriy . Springer-V erlag , 2000 . 151. K . S . Mr-Curley . \"Odds and Ends from Cryptology and Computational Num- ber Theory\", edited by C . Pomerance . Proceedings of Symposia in Applied 173. KIST, \"Data Encryption Standard' . Federal Information Processing Stan- Mathematics 42, American Mathematics Society . 1990, pp 49—74. dards Publication 46-3 . National Institute of Standards and Technology, U .S . Department of Commerce, 1999 . 152. R . J . McEliece, Finite Fields for Computer Scientists and Engineers, Kluwer Academic Publishers, 1987 . 174. I . Niven . H . S . Zuckerman and H . L . Montgomery, An Introduction to th e Theory of ' Numbers_ 5th Edition, John Wiley k Sons . 1991 . 153. H . McKean and V . Moll, Elliptic Curves Function Theory, Geometry, Arith- metic, Cambridge University Press ; 1997 . 175. D . H . Nyang and J . S . Song .. \"Fast Digital Signature Scheme Based oil th e Quadratic Residue Problem\" . Electronics Letters, 33 . 3(1997) . 205 206 . 154. A . R . Meijer, \"Groups, Factoring, and Cryptography\" Mathematics Magazine . 69 . 2(1996), 103 109 . 176. S . Pohlig and M . Hellman . \"An Improved Algorithm for Computing Loga- rithms over GF(p) and its Cryptographic Significance\", IEEE Transactions o n 155. V . J . Menezes. Elliptic Curve Public Key Crrptosystems, Kluwer Academi c Information Theory, 24 (1978), pp 106 110 . Publishers, 1993 . 177. J . O ' Connor and E . Robertson . The MacTutor History of Mathematics 156. A . Menezes and S . A . Vanstone, \" Elliptic curve cryptosystems and their im- Archive, http ://www .groups .dcs .st-and .ac .uk/history/VMathematicians . plementation \" , Journal of Cryptology, 6 (1993), 209-224 . 178. A . M . Odlyzko, \"Discrete Logarithms in Finite Fields and their Cryptographi c 1 .57 . A . Menezes . P . C . van Oorschot and S . A . Vanstone. Handbook of Applied Significance\", Advances in Cryptography . EUROCRYPT ' 84, Proceedings, Lec- Crvptosysterns. CRC Press . 1996 . ture Notes in Computer Science 209 . Springer-Verlag, 1984 . 225—314 . 158. R . C . Merkle . \"Secure Communications over Insecure Channels\" Communica- 179. T . Okamoto and K. Ohta, \"Universal Electronic Cash\", Advances in Cryp- tions of the ACM, 21 (1978) . 294—299 . (Submitted in 1975 . ) tography, CRYPTO '91, Proceedings . Lecture Notes in Computer Science 576 . Springer-Verlag, 1991 . 324337 . 159. J . F . Mestre, \"Formules Explicites et Minoration de Conducteurs de Varietes algebriques\" Compositio Mathematica, 58 (1986), 209 232 . 180. Open University Course Team . Number Theory. Complex Analysis Unit 15 , Open University Press, 1974 . 160. B . Meyer and and V . Muller . \"A Public Key- Cryptosystem Based on Ellipti c Curves over Z/nZ Equivalent to Factoring \" , Advancers in Cryptology, EURO- 181. O . Ore . Number Theory and its History. Dover Publications . 1988 . CRYPT ' 96 . Proceedings . Lecture Notes in Computer Science 1070 . Springer - V'erla.g1996, 49 59 . 182. C . P. Pfleeger . Security in Computing. Prentice-Hall . 1997. 161. M . Mignotte, \"How to Share a Secret \" . Cryptography, Workshop Proceedings , 183. R.G .E.Pinch, \"Some PrimalityTesting Algorithms Notices of the America n Lecture Notes in Computer Science 149, Springer-Verlag . 1983 . 371–375 . Mathematical Society. 40 . 9(1993), 1203 1210 . 162. G Miller . \"Riemann's Hypothesis and Tests for Pr'imality\", Journal of System s 184. R . G . E . Pinch . Mathematics for Cryptography, Queen's College . Universit y and Computer Science . 13 (1976) . 300 317 . of Cambridge, 1997 . 163. V . Miller_ \"Uses of Elliptic Curves in Cryptography \" , Advances in Cryptology. 185. R . G . E . Pinch . The Carmichael umbers up to 10 . Queen's College . Uni- CRYPTO '85 . Proceedings . Lecture Notes in Computer Science 218 . Springer- versity of Cambridge, 1997. Verlag, 1986 . 417 426 . 186. S . C . Pohlig and M . Helhnan . \" An Improved Algorithm for Computing Loga- 164. R . A . Mollin, Fundamental Number Theory with _Applications . CRC' Press . rithms over GF(p) and its Cryptographic Significance \" . IEEE Transactions o n 1998 . Information Theory, 24 (1978) . 106 110 . 165. R . A . Mollin . An Introduction to Cryptography, Chapman k Hall/CRC, 2001 . 187. J . M . Pollard . \"A Monte Carlo Method for Factorization\" . BIT. 15 (197 .5) , 331 3.32 . 166. P. L . Montgomery. \"Speeding Pollards and Elliptic Curve Methods of Fac- torization' Mathematics of Computation. 48 (1987), 243264. 188. J. M . Pollard . \"Monte Carlo Methods for Index Computation (mod p) ' , Mathematics of Computation . 32 (1980) . 918—924 . 167. P. L . Montgomery. \"A Survey of Modern Integer Factorization Algorithms \" , CWI Quarterly. 7. 4(1 .994) . 337 394 . 189. C . Pomerance . \"Very Short Primality Proofs \" . Mathematics of Computation , 48 (1987), 315-322 .

Bibliography Bibliography 42 5 424 190. C . Pomerance (editor), Cryptology and Computational Number Theory. Pro- 210. H . E . Rose, A Course in Number Theory . 2nd Edition, Oxford U ceedings of Symposia in Applied Mathematics 42 . American Mathematical So- Press, 1994 . ciety . 1990 . 211. K . Rosen, Elementary Number Theory and its Applications. 4th Edi in, 191. C . Pomerance, \"Cryptology and Computational Number Theory - An Intro- Addison Wesley, 2000 . duction \" , Cryptology and Computational Number Theory . edited by C . Pomer- ance, Proceedings of Symposia in Applied Mathematics 42 . American Mathe- 212. J . J . Rotman An Introduction to the Theory of Groups, Springer Verlag, 1994 . matical Society, 1990, 1 12 . 213. A . D . Rubin and D . E . Geer . Jr . . Mobile Code Security, IEEE Internet Com- 192. C . Pomerance, J . L . Selfridge and S . S . Wagstaff. Jr ., \"The Pseudoprimes t o puting, 2, 6(1998) . 30 34 . 25 . 109\" , Mathematics of Computation, 35 (1980), 1003-1026 . 214. G . Rozenberg and A. Salomaa, Cornerstones of Undecidabilitc, Prentice-Hall , 193. V . R . Pratt \"Every Prince Has a Succinct Certificate\" . SIAM Journal on 1994 . Computing. 4 (1975), 214-220 . 215. A . Salomaa . Public-Key Cryptography. 2nd Edition . Springer Verlag, 1996 . 216. Y . Saouter, Vinogradov's Theorem is True up to 10 20 , Publication Interne No . 194. W . H . Press and Teukolskv et al ., Numerical Recipes in C The Art of Scientific Computing, 2nd Edition, Cambridge University Press, 1992 . 977 . IRISA, 1995 . 217. V . Scarani . \"Quantum Computing\" , American ,Journal of Physics, 66 , 195. M. O . Rabin . \" Probabilistic Algorithms for Testing Primality \" , Journal of Number Theory . 12 (1980) . 128138 . 11(1998) . 956 960 . 218. B . Schneier, Applied Cryptography Protocols, Algorithms, and Source Cod e 196. E . D . Reilly and F . D . Federighi, P_ASCALGORITHMS A Pascal-Based Introduction to Computer Science, Houghton Mifflin, Boston, 1989 . in C, 2nd Edition, John Wiley & Sons . 1996 . 219. B . Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall and Niel s 197. D . Redmond, Number Theory: An Introduction . Marcel Dekker, New York. 1996 . Ferguson, The Twofish Encryption Algorithm . . John Wiley Sr. Sons, 1999 . 220. C . P. Schnorr, \"Efficient Identification and Signatures for Smart Cards\", Ad- 198. P . Ribenboim, The Little Book on Big Primes, Springer-Verlag, 1991 . vances in Cryptography, CRYPTO '89, Proceedings, Lecture Notes in Compute r 199. P . Ribenboim, \" Selling Primes\", Mathematics Magazine, 68, 3(1995), 175- Science 435, Springer-Verlag, 1990, 239-252 . 182 . 221. R . Schoof, \"Elliptic Curves over Finite Fields and the Computation of Squar e Roots mod p\", Mathematics of Computation, 44 (1985), 483 494 . 200. P . Ribenboim, The New Book of Prime Number Records, Springer-Verlag , 222. M . R . Schroeder, Number Theory in Science and Communication, 3rd Edition . 1996 . Springer Series in Information Sciences 7, Springer-Verlag, 1997 . 223. W . Schwarz and J . Wolfgang, \"Some Remarks on the History of' the Prim e 201. J . Richstein, \"Goldbach's Conjecture up to 4 . 1e\" , Mathematics of Compu- Number Theorem from 1896 to 1960\" Development of Mathematics 1900 1950, tation, 70, (2001) . 1745-1749 . edited by J .-P. Pier . Birkhauser . 1994. 224. A . Shamir, \"Factoring Numbers in O(logn) Arithmetic Steps \" , Informatio n 202. E . Rieffel and W . Polak, \"An Introduction to Quantum Computing for Non - Processing Letters, 8, 1(1979), 28-31 . Physicists\", ACM Computing Surveys . 32, 3(2000), 300 335 . 225. A . Shamir, \"How to Share a Secret\", Communications of the ACM, 22 . 11(1979), 612 613 . 203. H . J. J . te Riele, \"New Very Large Amicable Pairs\" , Number Theory . Noord- 226. P . Shor . \" Algorithms for Quantum Computation : Discrete Logarithms an d wijkerhout 1983, Proceedings, Lecture Notes in Mathematics 1068, Springer - Factoring\" . Proceedings of 35th Annual Symposium on Foundations of' Com- Verlag, 1984. 210-21 5 puter Science. IEEE Computer Society Press, 1994 . 124-134. 227. P . Shor . \"Polynomial-Time Algorithms for Prime Factorization and Discret e 204. H . J . J . te Riele, \"A New Method for Finding Amicable Numbers\", Reprin t Logarithms on a Quantum Computer\", SIAM Journal on Computing, 26 , from Mathematics of Computation 19-13-1993, A Half-century of Computationa l 5(1997), 1484 1509 . _Mathematics. Vancouver, 9-13 August 1993 . 228. J . H . Silverman and J . Tate, Rational Points on Elliptic Curves . Undergrad- uate Texts in Mathematics, Springer-Verlag . 1992 . 205. H . J . J . te Riele. \"Factorization of RSA-140 using the Number Field Sieve\" . 229. J . H . Silverman . The Arithmetic of Elliptic Curves. Graduate Texts in Math- http ://www .crypto-world .com/announcements/RSA140 .txt,4 February 1999 . ematics 106 . Springer-Verlag, 1994 . 230. J . H. Silverman ; A Friendly Introduction to Number Theory, Second Edition , 206. H . J . J . te Riele, \"Factorization of a 512-bits RSA Key using the Numbe r Prentice-Hall . 2001 . Field Sieve\" , http ://www .crypto-world .com/announcements/RS11155 .txt, 26 231. J . H . Silverman . \" The Xedni Calculus and the Elliptic Curve Discrete Loga- August 1999 . rithm Problem\" , Dept of Mathematics . Brown University . 10 February 1999 . 207. H . Riesel . Prime Numbers and Computer Methods for Factorization . Birkhauser, Boston . 1990 . 208. R . L . Rivest . \"Remarks on a Proposed Cryptanalytic Attack on the M .I .T . Public-key Crvptosystem\" . Crtiptologia ., 2, 1(1978) . 62 65 . 209. R . L . Invest, A . Shamir and L . Adleman, A Method for Obtaining Digita l Signatures and Public Kev Crvptosysterns . Communications of the ACM, 21 . 2(1978) . 120 126 .

Bibliograph Bibliography 42 7 426 232. J . H . Silverman and J . Suzuki . \" Elliptic- Curve Discrete Logarithms and th e 255. H . C . Williams . \"The Influence of Computers in the Development of Number Index Calculus, Advances in Cryptology ASIACR PT ' 98 . Springer Lectur e Theory - . Computers & Mathematics with A pplications, 8 . 2(1982) . 75-93 . Notes in Computer Science 1514, 1998 . 110-125 . 256. H . C . Williams . \" Factoring on a Compute{, Mathematical Intelligencer . 6 , 233. R . D . Silv erman . 'The Multiple Polynomial Quadratic Sieve\" . Mathematics o f 3(1984), 29 36 . Computation . 48 (1987) . 329 339 . 257. H . C . Williams . Edouard Lucas and Prima litc Testing. John Wiley & Sons . 234. R . D . Silverman, \"A Perspective on Computational Number Theory Notice s 1998 . of the American Mathematical Society. 38, 6(1991) . 562 568 . 258. C . P. Williams and S . H . Clearwater . Explorations in Quantum Computation . 235. R . D . Silverman, \"Massively Distributed Computing and Factoring Large In- The Electronic Library of Science (TELOS) . Springer-Verlag, 1998 . tegers\", Communications of the ACM. 34 . 11(1991) . 95-103 . 259. H . VV'oll . \"Reductions Among Number Theoretic Problems\" . Information an d 236. D . R . Simon, \"On the Power of Quantum Computation\" . Proceedings of th e Computation . 72 (1987) . 167-179 . 35th Annual IEEE Symposium on Foundations of Computer Science, IEE E Press, 1994 . 116 123 . 260. S . Y . Yan . \"Primality Testing of Large Number s n Maple' . Computers & Mathematics with Applications, 29 . 12(1995) . 18 . 237. S Singh . The Code Book The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Fourth Estate, London, 1999 . 261. S . Y. Yan, Perfect, Amicable and Sociable Numbers A Computational Ap- proach, World Scientific, 1996 . 238. S . Singh. The Science of Secrecy The Histroy of Codes and Codebreakrng , Fourth Estate, London, 2000 . 262. S . Y . Yan, An Introduction to Formal Languages and _Machine Computation . World Scientific, 1998 . 239. Al . K . Sinisalo, \"Checking the Goldhach Conjecture up to 4 10 11\" . Mathe- matics of Computation . 61 (1993) . 931934 . 263. J . Young . \"Large Primes and Fermat Factors\" . Mathematics of' Computation , 67 (1998) . 1735 1738 . 240. M . Sipser, Introduction to the Theory of Computation, PW'S Publishing Com- pany, Boston, 1997 . 264. R . Yuan and W . T . Strayer . Virtual Private Networks Technologies an d Solutions, Addison-Wesley. 2001 . 241. D . Slowinski . \" Searching for the 27th Mersenne Prime\" . Journal of Recre- ational Mathematics, 11 . 4(1978-79), 258-261 . 265. K . C . Zeng, C . H . Yang . D . Y . Wei and T . R . N . Rao, \" Pseudorandom Bi t Generators in Stream-Cipher Cryptography\", Computer, 24, 2(1991) . 8-17 . 242. R . E . Smith . Internet Cryptography . Kluwer Academic Publishers, 1997 . 243. M . A . Soderstrand, W . K. Jenkins, G . A. Jullien and F . J . Taylor, Residu e Number System Arithmetic, Modern Applications in Digital Signal Processing, IEEE Press . 1986 . 244. R . Solovay and Y . Strassen, \"A Fast Monte-Carlo Test for Primality\", SIA M Journal on Computing, 6, 1(1977) . 84 85 . \"Erratum : A Fast Monte-Carlo Test for Primality- \" . SIAM Journal on Computing. 7 . 1(1978), 118 . 245. I . Stewart . \"Geometry Finds Factor Faster\", Nature . 325 . 15 January 1987 . 199 . 246. D . R . Stinson, Cryptography: Theory and Practice. CRC Press . 1995 . 247. N. S . Szabo and R. I . Tanaka, Residue Arithmetic and its Applications to Computer Technology . McGraw-Hill, 1967 . 248. H . C . A . van Tilborg . An Introduction to Cryptography, Kluwer Academi c Publishers . 1988 . 249. I . A ardi, Computational Recreations in Mathematica . Addison-Wesley, 1991 . 250. M . VV'aldschmidt . P . Moussa. .1 . M . Luck and C . Itzykson . From Number The- ory to Physics . Springer-Verlag, 1.992 . 251. S Wagon . \"Primality Testing\", The Mathematical Intelligencer. 8 . 3(1986) . 58-61 . 252. D . Welsh . Codes and Cryptography . Oxford University Press . 1989 . 253. H . Wiener . °Crvptanalvsis of Short RSA Secret Exponents, IEEE Transac- tions on Information Theory. 36 . 3(1990) 553558 . 254. A . Wiles, 'Modular Elliptic Curves and Fermat 's Last Theorem \" . Annals o f Mathematics . 141 (1995) . 443-551 .

Inde x (k . n)-threshold scheme, 39 9 Al-Khwarizmi, 17 7 R(x), 10 3 algebraic computation law . 16 4 EX P . 18 2 algebraic equation . 5 4 A' P . 18 2 algebraic numbers . 1 5 .VP-complete, 18 7 algorithm . 23 . 177 A - P-hard . 18 7 aliquot k-cycle, 7 1 P, 18 2 alphabet ; 183 .1(n) . 9 2 amicable k-tuple, 7 1 ),(n), 8 1 amicable pair, 71 . 176, 29 2 µ(n), 8 2 amicable triple, 71 0(n), 7 9 APR test, 22 6 x, 17 6 APRCL test, 22 6 7(x), 86 arithmetic function . 6 3 712(x) . 10 6 arithmetic mean, 70 7ru(x), 3 6 arithmetic progression of primes, 110 , ri(x), 9 2 o(n), 66 17 6 T(n), 6 6 associativity, 1 6 9(x), 9 0 asymmetric cryptosystems, 33 3 c(s), 9 5 asymmetric key crvptosystem, 35 1 b-sequence, 20 9 Atkin, A . O . L ., 22 3 kth (higher) power nonresidue, 15 7 authentication . 332 kth (higher) power residue, 15 7 kth power nonresidue, 13 5 base-2 pseudoprimality test, 20 8 kth power residue, 13 5 basis vector, 274 nth prime . 10 5 Bernoulli ' s number . 9 6 s(n), 6 6 binary computers . 31 2 .VP-SPACE, 18 4 binary Goldbach conjecture . 8, 295 P-SPACE . 18 4 binary operation . 1 5 Li(x) . 9 4 bit operation, 191 block cipher . 33 8 Abel, N . H . . 1 6 Brent . R. P., 24 8 adder . 31 6 Bruns constant . 108 additive group . 1 6 additive identity. 1 9 Caesar cipher . 33 6 additive inverse, 1 9 Caesar . J . . 33 6 additivitv. 6 Carmichael number . 20 7 Adleman . L . . 35 8 Carmichael ' s A-function . 81 . 12 7 Advanced Encryption Standard (AES) , Carmichael ' s theorem, 12 7 Carmichael . R . D ., 8 1 34 7 CFRAC factoring algorithm, 23 9 affine transformation . 337 CFRAC method . 237

43 0 Index Index Chin Chiu-Shan . 112 . 130 covered writing, 409 efficient (good) algorithm, 18 4 fast modular exponentiations, 19 6 character cipher . 33 5 cryptanalysis . 33 2 electronic commerce. 40 5 fast point additions . 19 9 Chebvshev's function, 9 0 cryptographic tunnels . 404 ElGatnal crvptosystem, 35 6 Federal Information Processin g Chebyshev . P . L . . 90 cryptography. 332 elliptic curve, 160 . 37 9 check digit . 32 2 cryptology . 33 2 elliptic curve analogue of Diffie – Standard . 34 4 Chen, J . R., 9, 109 cubic Diophantine equation . 16 0 Fermat numbers, 36, 17 5 Chinese Remainder Theorem (CRT) , cyclic group, 1 7 Hellman . 381 Fermat probable prime, 20 6 elliptic curve analogue of ElGamal . 38 2 Fermat pseudoprime . 20 6 130, 395 . 39 9 Data Encryption Standard (DES) . 344 . elliptic curve analogue of Massey– Fermat 's factoring algorithm . 23 4 Chinese test . 20 8 36 7 Fermat's Last Theorem (FLT) . 12 Church, A . . 18 0 Omura . 38 1 Fermat's little theorem_ 12 5 Church-Turing thesis . 18 0 database decryption . 39 7 elliptic curve analogue of R.SA, 38 2 Fermat's pseudoprimality test . 20 6 ciphertext space, 33 3 database encryption, 39 6 elliptic curve bit generator, 33 1 Fermat . P. . 1 2 closure, 1 5 database security . 39 5 elliptic curve cryptography (ECC), 37 9 Fevnman, R . P. . 273 Cocks, C . C ., 35 0 De la Vallee Poussin, C . J . . 9 1 Elliptic Curve Digital Signatur e Fibonacci numbers, 21 6 coin tossing states . 179 decidable, 178 Fibonacci . L . P . . 21 6 collision resistant . 32 1 decision problem, 18 3 Algorithm (ECDSA) . 39 4 field . 1 8 combined test, 21 8 decryption key, 33 3 elliptic curve discrete logarith m finite fields . 2 0 common multiple . 3 1 decryption process (algorithm), 33 3 finite group, 1 6 commutative group . 1 6 deterministic encryption . 37 3 problem (ECDLP), 26 6 finite order of a point on an ellipti c commutative ring, 1 8 Deutsch . D . . 273 elliptic curve test . 22 2 commutativity . 1 6 Dickson . L . E ., 30 3 elliptic function . 16 2 curve . 168 complement . 18 3 Diffie . W ., 348 elliptic integral, 16 2 finite simple continued fraction . 4 6 complete quotients . 5 1 Diffie-Hellman-Merkle key-exchange , Ellis . J . H . . 35 0 FIPS 186, 39 2 complete system of residues . 11 5 embedded message, 40 9 FIPS 46, 344 completely multiplicative function . 6 4 35 4 embedding messages on elliptic curves . FIPS 46-2 . 344 complex numbers, 1 5 Digital Signature Algorithm (DSA) , FIPS 46-3 . 344 complex zeros . 9 8 38 0 firewall, 40 3 complexity classes . 183 39 2 encryption key, 333 fixed-base number systems . 30 5 composite Fermat numbers. 3 6 Digital Signature Standard (DSS) . 39 2 encryption process (algorithm), 33 3 fixed-point attack, 37 2 composite number, 2 4 digital signatures . 385 ENIGMA code . 33 3 Fundamental Theorem of arithmetic , computable . 17 8 Diophantme equation, 5 3 equivalence classes, 11 3 computation. 18 0 Diophantus, 5 2 equivalence relation . 11 3 28, 30 5 computationally intractable (o r Dirac . P. A . M . . 274 Eratosthenes of Cvrene . 2 6 Dirichlet characters, 10 2 Eras, P., 9 3 Galileo spacecraft, 32 5 infeasible) . 18 5 Dirichlet L-fimctions, 10 2 error detection and correction . 32 1 Galois field . 2 0 computationally tractable (or feasible) , Dirichlet series . 10 2 Euclid . 2, 2 4 Dirichlet, J . P . G . L ., 10 1 Euclid's algorithm . 40, 41 Galois . E, 2 0 18 5 discrete exponential bit generator, 33 1 Euclid 's Elements, 4 2 Gauss's lemma, 14 1 congruence . 11 1 discrete exponential generator, 33 0 Euclid Euler Theorem, 7 2 Gauss . C . F . 8 9 congruence classes . 11 3 discrete logarithm . 15 6 Eisler probable prime, 21 4 Generalized Riemann Hypothesis, 10 2 congruent. 11 2 discrete logarithm problem . 254 . 35 3 Euler pseudoprirne, 21 4 generating function . 10 2 consecutive pairs of quadratic residues , Disquisitiones Arithmeticae . 11 1 Eider ' s (totient) d-function, 7 9 geometric composition law . 16 4 dividend . 2 3 Elder's criterion . 13 9 geometric mean . 6 8 13 6 divisibility. 2 1 Euler's pseudoprimality test . 21 4 Goldbach partition . 1 0 consecutive triples of quadrati c division algorithm, 2 3 Eider's rule for amicable pairs, 7 7 Goldbach's conjecture . 6 . 176 . 29 5 division ring . 1 8 Euler's theorem . 126 Goldwasser . S . . 22 2 residues . 13 7 divisor, 2 1 Euler . L . . 7 7 greatest common divisor (gcd) . 2 9 continued fraction, 44 domain . 6 3 even number . 2 4 group, 1 5 Continued FRACtion (CFRAC ) double encryption . 34 6 exclusive or (XOR) . 34 4 group laws on elliptic curves, 16 8 double hash . 31 8 exponential complexity. 19 3 method . 23 0 exponentially bounded . 18 2 Hadanrard . .J . . 9 1 convergent . 45 ECPP (Elliptic Curve Primality exponentially solvable . 18 2 halting problem, 18 1 convergents, 5 5 Proving), 22 3 extended Euclid's algorithm . 12 2 Hardy, G . H . . 8 Converse of Fermat ' s little theorem _ Hardy Rarnanujan taxi number . 1 0 ECPP Algorithm, 22 4 factor . 2 1 harmonic mean, 7 0 12 6 effective procedure. 177 factoring by trial divisions, 23 2 hash function, 317 Converse of Wilso n ' s theorem . 12 8 fast group operations . 199 Cook . S ., 18 6 Cook Karp Thesis, 186

Index Index 43 1 430 Ch'in Chiu-Shao . 112 . 13 0 covered writing. 40 9 efficient (good) algorithm, 18 4 fast modular exponentiatfons . 196 character cipher, 33 5 c ryptanalvsis, 33 2 electronic commerce, 40 5 fast point additions, 19 9 Chebvshev's function . 9 0 cryptographic tunnels .. 40 4 ElGamal cryptosystem, 35 6 Federal Information Processing Chebvshev . P . L . . 9 0 cryptography. 33 2 elliptic curve . 160 . 379 check digit . 32 2 cryptology, 33 2 elliptic curve analogue of Diffie– Standard . 344 Chen, J . R . . 9 . 10 9 cubic Diophantine equation. 16 0 Fermat numbers . 36 . 17 5 Chinese Remainder Theorem (CRT) . cyclic group . 1 7 Hellman, 38 1 Fermat probable prime . 20 6 elliptic curve analogue of ElGamal . 38 2 Fermat pseudoprime . 20 6 130 . 395 . 399 Data Encryption Standard (DES), 344 . elliptic curve analogue of Masse y Fermat's factoring algorithm, 23 4 Chinese test . 20 8 36 7 Fermat ' s Last Theorem (FLT), 1 2 Church . A . . 18 0 Omura, 38 1 Fermat's little theorem, 12 .5 Church-Turing thesis, 18 0 database decryption . 39 7 elliptic curve analogue of RSA . 38 2 Fermat's pseudoprimality test . 206 ciphertext space, 33 3 database encryption . 39 6 elliptic curve bit generator . 33 1 Fermat, P . . 1 2 closure . 1 5 database security. 39 5 elliptic curve cryptography (ECC) . 379 Feynman . R . P . . 27 3 Cocks . C . C ., 35 0 De la Vallee-Poussin . C . J ., 9 1 Elliptic Curve Digital Signatur e Fibonacci numbers . 21 6 coin tossing states . 17 9 decidable, 17 8 Fibonacci . L . P., 21 6 collision resistant, 32 1 decision problem . 18 3 Algorithm (ECDSA) . 394 field, 18 combined test, 218 decryption key. 333 elliptic curve discrete logarith m finite fields, 20 common multiple, 3 1 decryption process (algorithm) 33 3 finite group . 1 6 commutative group . 1 6 deterministic encryption . 373 problem (ECDLP) . 26 6 finite order of a point on an ellipti c commutative ring, 1 8 Deutsch, D . . 27 3 elliptic curve test, 22 2 commutativity, 1 6 Dickson . L . E . . 30 3 elliptic function . 16 2 curve . 16 8 complement, 18 3 Diffie . AV . . 348 finite simple continued fraction . 46 complete quotients. 51 Diffie-Hellman-Slerkle key-exchange, elliptic integral . 16 2 FIPS 186 . 39 2 complete system of residues, 11 5 Ellis . J . H . . 3 .5 0 FIPS 46, 344 completely multiplicative function, 6 4 35 4 embedded message, 40 9 FIPS 46-2 . 34 4 complex numbers, 1 5 Digital Signature Algorithm (DSA) . embedding messages on elliptic curves , FIPS 46-3, 34 4 complex zeros . 9 8 fnewall . 40 3 complexity classes . 18 3 39 2 380 fixed base number systems, 30 0 composite Fermat numbers . 3 6 Digital Signature Standard (DSS) . 39 2 encryption key, 33 3 fixed-point attack. 372 composite number . 24 digital signatures . 38 5 encryption process (algorithm) . 33 3 Fundamental Theorem of Arithmetic , computable. 17 8 Diophantine equation . 5 3 ENIGMA code, 333 computation, 18 0 Diophantus, 5 2 equivalence classes . 11 3 28 . 30 5 computationally- intractable (o r Dirac, P . A . M . . 27 4 equivalence relation . 11 3 Dirichlet characters, 10 2 Eratosthenes of Cyrene_2 6 Galileo spacecraft, 32 0 infeasible), 18 5 Dirichlet L-functions, 10 2 Erdos . P . . 9 3 Gatos field, 2 0 computationally tractable (or feasible) , Dirichlet series . 10 2 error detection and correction, 32 1 Dirichlet, J . P . G . L . . 10 1 Euclid, 2 . 2 4 Galois . E . 2 0 18 .5 discrete exponential bit generator . 33 1 Euclid's algorithm . 40, 41 Gauss ' s lemma . 141 congruence . 11 1 discrete exponential generator, 33 0 Gauss . C . F . . 8 9 congruence classes, 11 3 discrete logarithm . 15 6 Euclid's Elements, 4 2 Generalized Riemann Hypothesis . 102 congruent . 11 2 discrete logarithm problem . 254, 35 3 Euclid–Euler Theorem . 72 generating function . 10 2 consecutive pairs of quadratic residues . Disquisitiones Arithmeticae . 11 1 Euler probable prime . 21 4 geometric composition lax, 16 4 dividend . 2 3 Euler pseudoprime . 21 4 geometric mean . 6 8 13 6 divisibility, 21 Euler's (totient) q function, 7 9 Goldbach partition . 1 0 consecutive triples of quadrati c division algorithm . 23 Eukr's criterion, 13 9 Goldbach's conjecture. 6 . 176 . 29 5 division ring . 1 8 Euler's pseudoprimality test . 21 4 Goldwasser . S . . 22 2 residues . 13 7 divisor, 2 1 Euler's rule for amicable pairs, 7 7 greatest common divisor (gcd) . 2 9 continued fraction . 44 domain 6 3 Euler's theorem . 12 6 group . 1 5 Continued FR ACtion ((FR AC) double encryption . 34 6 Eviler, L . . 7 7 group laws on elliptic curves. 168 double hash . 31 8 even number . 2 4 method . 23 0 exclusive or (NOR), 34 4 Hadamard . J . . 9 1 convergent . 4 5 ECPP (Elliptic Curve Pr exponential complexity, 19 3 halting problem, 18 1 convergents . 55 Proving) . 22 3 exponentially bounded, 182 Hardy. G . H . . 8 Converse of Fermat 's little theorem . exponentially solvable, 182 Hardy Ramanujan taxi number . 1 0 ECPP Algorithm, 22 4 extended Euclid 's algorithm . 12 2 harmonic mean . 70 12 6 effective procedure, 177 hash function, 317 Converse of \\Vilson ' s theorem . 12 8 factor . 2 1 Cook . S . . 18 6 factoring by trial divisions . 232 Cook-Karp Thesis, 186 fast group operations, 199

Index Index 43 432 Hasse . H . 16 9 Lehman 's method . 22 9 Morain . F . . 22 3 polarization, 41 0 height of a point, 16 6 Lehner, D . H . . 21 8 Mordell, L . J ., 170 Pollard's p factoring algorithm, 24 8 Hellman, M . E . . 34 8 Lenstra's Elliptic Curve Metho d multiple, 2 1 Pollard's p-method . 230, 244 high-order congruence . 13 3 multiple encryption, 346 Pollard's \"p - 1\" factoring algorithm . Hilbert space . 274 (ECM), 230, 25 1 Multiple Polynomial Quadratic Sieve hybrid cryptosystem, 35 4 Lenstra, H. W . Jr_ . 25 1 25 0 linear congruence . 12 3 (MPQS) . 23 0 Pollard's \"p - 1 \" method . 250 identity, 1 6 linear Congruential generator, 32 7 multiplicative function . 6 4 Pollard, J . M ., 244 incongruent . 11 2 linear Diophantine equation . 5 4 multiplicative generator, 32 8 polygraphic cipher, 33 8 index calculus . 26 2 Littlewood, J. E . . 8 multiplicative group, 1 6 polynomial bounded, 18 2 index of a to the base q . 15 6 logarithm . 18 9 multiplicative identity . 1 9 polynomial complexity . 19 3 index of an integer modulo n . 15 5 logarithmic integral, 9 4 multiplicative inverse, 19 . 12 0 polynomial congruence . 13 3 inefficient (bad) algorithm) . 184 Lucas numbers, 21 6 multiplicativity. 5 polynomial congruential equation, 133 infinite fields, 2 0 Lucas probable prime . 21 7 polynomial security. 37 3 infinite group, 1 6 Lucas pseudoprimality test, 21 8 National firstitute of Standards an d polynomially solvable, 18 2 infinite order of a point on an ellipti c Lucas pseudoprinre . 21 7 Technology (KIST), 344 Pomerance, C . . 24 0 Lucas sequences, 21 5 positional number systems . 30 5 curve . 16 8 Lucas test, 217 natural numbers, 1 4 positive integers, 14 infinite simple continued fraction . 4 8 Lucas theorem, 21 7 non secret cover-message, 40 9 power generator . 32 9 instantaneous description (ID), 18 0 Lucas . F . E . . 21 5 non-secret encryption, 35 1 practically feasible computation, 18 2 Integer, 1 4 Lucas -Lehmer test, 21 8 non-zero field element, 1 9 practically tractable computation, 18 2 integer factorization problem, 228, 35 2 Lucas-Lehner theorem, 21 9 noncomputable, 17 8 primality, 4 integral domain, 1 8 Lucas-Lehmer test for Mersenn e nonnegative integers, 1 4 primality testing problem, 20 2 International Standard Book Number nonpositional number systems . 30 5 prime counting function, 8 6 primes, 22 0 nontrivial divisor . 2 2 prime distribution function, 8 6 (ISBN), 32 2 nontrivial square root of 1, 20 9 prime factor, 27 Internet, 40 3 Mobius p.-function, 8 2 nontrivial zeros, 9 8 prime factorization, 5 inverse, 1 6 Mobius inversion formula, 83 nonrritness, 21 3 prime Fermat numbers, 3 6 invertible function, 35 2 Mobius . A . F ., 8 2 Number Field Sieve (NFS), 5 . 230, 242 , prime number. 2 4 irrational number . 1 5 magnitude, 31 5 Prime Number Theorem, 8 8 irrational numbers, 48 Massey-Omura crJ ptosystem, 35 7 265 prime numbers, 8 5 isomorphic, 30 9 Meissel, D . F . E . . 28 7 number systems, 30 5 prime power, 20 isomorphism, 30 9 Menezes, A . J . . 38 3 prime power decomposition, 2 8 Merkle, R . C . . 34 9 odd number, 2 4 prime triples . 4 Jacobi symbol, 14 7 Mersenne number . 3 3 odd perfect numbers, 17 5 primitive root of n. 15 2 Jacobi, C . G . . 147 Mersenne primes. 34 . 17 5 Odlyzko, A . M . . 78, 28 8 principle of superposition, 275 Mersenne, M ., 3 3 one's complement representation, 31 6 privacy . 33 2 Karp . R., 18 6 Mertens's conjecture . 7 8 one-way function . 35 2 private key . 35 2 key bundle . 346 message concealing, 41 0 one-way hash function . 32 1 probabilistic encryption . 373 . 37 5 key space, 33 3 message digest . 321 . 39 2 order of a modulo n . 15 1 probabilistic Turing machine (PTM) , Kilian, J ., 22 2 message extracting . 41 0 order of a field, 2 0 Knuth . D . E . . 22 9 message space . 333 order of a group, 1 7 17 9 Koblitz, N . 37 9 middle-square method, 32 6 order of a point on an elliptic curve . probable prime, 206 Kronecker. L . . 1 4 Miller, G . . 21 0 proper divisor . 21 Miller-Rabin test . 21 0 16 8 pseudoprime, 20 6 Lagarias, J . C . . 28 8 minimal perfect hash function . 32 0 pseudorandom numbers . 32 6 Landau . E . . 8 minimal collision-free hash function . packer filter . 40 3 public key . 35 2 language . 18 3 parity. 2 public-key cryptography. 333 least (nonnegative) residue of z modul o 32 0 parity check . 3 . 32 1 public. key cryptosystem . 354 mixed-base number systems. 30 5 parity check bit . 32 1 purely periodic simple continued n . 11 4 modular arithmetic in Z/nZZ, 118 partial quotients . 4 5 least common multiple (lcm) . 3 1 modular exponentiation . 19 5 Pell ' s equation . .5 7 fraction, 5 0 least nonnegative residue . 11 2 modular inverse . 12 0 perfect hash function, 32 0 Pythagoras, 7 6 least residue. 14 1 modulus . 11 2 perfect number, 7 1 Legendre symbol . 13 9 monographic cipher, :33 5 period . 5 0 quadratic congruence, 13 4 Legend re's congruence, 234 inonoid, 16 periodic simple continued fraction, 5 0 quadratic Diophantine equation, 57 Legendre . A . _M . . 89 . 139 Pocklington ' s theorem, 222, 370 point at infinity, 161

43 4 Index Index quadratic irrational . 5 0 residue classes . 11 3 standard prime factorization, 2 8 Triple DES (TDES) . 346 quadratic nonresidue, 13 5 residue classes modulo rz . 1 5 steganographic system, 41 0 trivial divisor. 2 2 quadratic nonresidue modulo n, 35 3 residue computers . 31 3 steganography, 40 9 trivial zeros . 98 Quadratic reciprocity law, 14 4 residue number systems. 305 . 31 2 stego-key-, 40 9 Tukey, J . W ., 282 quadratic residue, 13 5 residue of .r modulo n, 11 3 stego-message, 409 Turing machine, 178 quadratic residue modulo n . 35 3 residue representation of a number . 30 6 Strassen, V . . 22 6 Turing . A . M . . 178 quadratic residues generator, 33 0 Riemann (-function, 9 5 strong probable prime, 210 Twin Prime Conjecture . 109 Quadratic Residuosity Problem (QRP) , Riemann function . 10 3 strong pseudoprimality test, 208, 21 0 twin primes, 4, 8 5 Riemann Hypothesis (RH) . 98, 17 6 strong pseudoprime . 21 0 two's complement representation, 31 6 353 . 37 4 Riemann, G . F . B, 91, 9 5 strong test, 20 8 Quadratic Sieve (QS) . 24 0 ring, 1 7 subexponential complexity, 23 1 U .S . National Institute of Standard s quantum algorithm for discrete ring with identity, 1 8 subgroup . 1 7 and Technology (NIST), 39 2 Rivest . R . L ., 35 8 substitution cipher, 33 5 logarithms, 28 5 root finding problem . 271, 372 sunrmatory function of .1(n) . 9 2 undecidable . 178 quantum algorithm for intege r RSA Assumption, 358 Sun Zi, 130 unsolvable. 17 8 RSA bit generator, 33 1 superposition, 27 7 factorization, 28 2 RSA cryptosystem, 35 8 symmetric, 11 3 Vanstone, S . A ., 383 quantum bit, 274 RSA generator, 32 9 symmetric cryptosystems, 333 \\- inogradov . I . M . . 9 quantum computer . 274 . 27 6 running time, 18 2 Virtual Private Networks, 40 5 quantum cryptography, 41 0 Taylor . R .. . 1 2 von Mangoldt function, 9 2 quantum operation. 277 secret key . 333 . 35 2 te Riele ' s rule, 78 von Neumann, .J ., 32 6 quantum register, 276 . 28 2 secret sharing . 399 te Riele . H . J . J . . 7 8 quantum state . 274 secret-key cryptography, 33 3 ternary Goldbach conjecture, 8, 29 5 Waring's problem, 176 quantum Turing machine (QTM) . 278 secret-key cryptosystem, 35 4 Thabit ibn Qurra, 74 Wiener's attack, 37 2 qubit, 27 8 Selberg's estimate, 9 2 Thabit's rule for amicable pairs, 7 5 Wiles . A . J ., 11 . 1 2 quotient . 2 3 Selberg, A . . 9 2 time complexity function, 18 2 Williamson, M . J ., 35 1 Selfridge, J . L . . 21 0 torsion subgroup, 17 1 Wilson's theorem . 12 8 Rabin's modified bit generator, 33 1 semantic security. 373 transcendental numbers . 1 5 Wilson, J ., 12 8 Rabin . M . O . . 21 0 semigroup, 1 6 transitive . 11 3 witness, 21 3 Ramanujan, S ., 1 0 seminumerical method, 29 3 trapdoor, 35 2 words . 31 5 random number generation, 32 6 Shamir, A ., 35 8 trapdoor one-way function, 35 2 write-keys, 39 6 random numbers . 32 6 Shanks' baby-step giant-step metho d trial division . 230 randomized encryption . 37 3 xedni calculus . 267 rank of an elliptic curve . 17 1 for discrete logarithms . 25 6 rational numbers . 15 . 4 6 Shanks ' class group method, 22 9 read-keys, 39 6 Shanks' SQUFOF method, 22 9 real number . 5 0 Shanks, D ., 25 5 real numbers, 1 5 Shannon bits, 274 real zeros, 9 8 Shannon . C. E . . 19 0 real-valued function . 63 shift transformation . 33 7 realbase logarithm, 15 5 Shot, P., 28 1 rectilinear polarization, 410 Sieve of Eratosthenes. 2 6 reduced system of residues modulo n . sign bit . 31 5 signature generation, 39 2 11 7 signature verification, 39 2 reflexive, 11 3 signed-magnitude representation, 31 5 relatively prime . 30 Silver-PohligHellman algorithm, 25 8 remainder . 2 3 simple continued fraction, 4 5 repeated doubling and addition, 19 9 sociable group . 7 1 repeated doubling method, 380 Solovay, R . . 22 6 repeated multiplication, 19 5 Solovay-Strassen test . 21 4 repeated squaring, 19 5 solvable . 17 8 repeated squaring and multiplication , square generator, 33 0 square root method . 258 195 residue, 11 2 residue arithmetic in (TG/nZ) ` , 31 1 residue class . 113