Bibliography

[1] C. Adams and S. Farrell, Internet X.509 public key infrastructure: Certi¬-
cate management protocols, Internet Request for Comments 2510 (March
1999).
[2] C. Adams and S. Lloyd, Understanding Public-Key Infrastructure,
New Riders Publishing, Indianapolis, Indiana (1999).
[3] W. R. Alford, A. Granville, and C. Pomerance, There are in¬nitely many
Carmichael numbers, Ann. Math. 140 (1994), 703“722.
[4] N.C. Ankeny, The least quadratic nonresidue, Ann. of Math. 55 (1952),
65“72.
[5] ANSI X9.17, American National Standard ” Financial institution key
management (wholesale), ASCX9 Secretariat ” American Bankers Asso-
ciation (1985).
[6] ANSI X9.57, Public key cryptography for the ¬nancial service industry ”
Certi¬cate management (1997).
[7] C. Asmuth and J. Bloom, A modular approach to key safeguarding, IEEE
Trans. Inf. Theor. IT-30 (1983), 208“210.
[8] A.O.L. Atkin and R.G. Larson, On a primality test of Solovay and Strassen,
Siam J. Comp. 11 (1982), 789“791.
[9] D. Atkins, M. Gra¬, A.K. Lenstra, and P.C. Leyland, The magic words are
SQUEAMISH OSSIFRAGE in Advances in Cryptology, ASIACRYPT
™94, Springer-Verlag, Berlin, LNCS 917, (1995), 263“277.
[10] D. Atkins, W. Stallings, and P. Zimmerman, PGP Message Exchange For-
mats, Internet Request for Comments 1991 (August 1996).
[11] M. Aydos, T. Yanik, and C.K. Ko¸, High-Speed implementation of an ECC-
¸ c
based wireless authentication protocol on an ARM microprocessor, IEEE
Proc. Commun.148 (2001), 273“279.
[12] A. Aziz and W. Di¬e, Privacy and authentication for wireless local area
networks, IEEE Personal Commun. 1 (1994), 25“31.

249
© 2003 by CRC Press LLC
250 RSA and Public-Key Cryptography

[13] E. Bach, Analytic methods in the analysis and design of number-theoretic al-
gorithms (A distinguished ACM dissertation) MIT Press, Cambridge, Mas-
sachusetts (1985).
[14] E. Bach, Explicit bounds for primality testing and related problems, Math.
Comp. 55 (1990), 355“380.
[15] E. Bach and J. Shallit, Algorithmic Number Theory, 1, MIT Press,
Cambridge, Massachusetts (1997).
[16] F.L. Bauer, Decrypted Secrets, Springer, Berlin (1997).
[17] A. Beimel and B. Chor, Secret sharing with public reconstruction, in Ad-
vances in Cryptology, in CRYPTO ™95, Springer-Verlag, Berlin, LNCS
963 (1995), 353“366.
[18] E.T. Bell, Men of Mathematics, Simon and Schuster, New York (1937).
[19] M. Bellare and P. Rogaway, Optimal asymmetric encryption in Advances in
Cryptology, EUROCRYPT ™94, Springer-Verlag, Berlin, LNCS 950 (1994),
92“111.
[20] M.J. Beller, L.F. Chang, and J. Yacobi, Privacy and authentication on
a portable communications system, IEEE J. Selected Areas Commun. 11
(1993), 821“829.
[21] M.J. Beller and Y. Yacobi, Fully-¬‚edged two-way public-key authentication
and key agreement for low cost terminals, Electron. Lett. 29 (1993), 999“
1001.
[22] S.M. Bellovin and M. Merritt, Encrypted key exchange: Password-based
protocols secure against dictionary attacks, in Proceedings of the 1992 IEEE
Computer Society Conference on Research in Security and Privacy (1992),
72“84.
[23] S.M. Bellovin and M. Merritt, Cryptographic protocol for secure communi-
cations, U.S. Patent 5241599, August 31 (1993).
[24] D.J. Bernstein, Faster square roots in annoying ¬nite ¬elds, preprint.
[25] D.J. Bernstein, The multiple-lattice number ¬eld sieve, preprint.
[26] E. Biham and A. Shamir, Di¬erential Cryptanalysis of the Data En-
cryption Standard, Springer-Verlag, New York (1993).
[27] G.R. Blakely, Safeguarding cryptographic keys, Proc. National Computer
Conf., American Federation of Information Processing Societies 48 (1979),
242“268.
[28] G.R. Blakely and G.A. Kabatianski, On general perfect secret sharing
schemes, in Advances in Cryptology, CRYPTO ™95, Springer-Verlag,
Berlin, LNCS 963 (1995), 367“371.


© 2003 by CRC Press LLC
Bibliography 251

[29] R. Blom, An optimal class of symmetric key generation systems, EURO-
CRYPT ™84, Springer-Verlag, Berlin, LNCS 209 (1985), 335“338.
[30] M. Blum, Coin ¬‚ipping by telephone: A protocol for solving impossible
problems, in Proceedings of the 24th IEEE Computer Conference, IEEE
Press (1982), 133“137.
[31] C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung,
Perfectly-secure key distribution for dynamic conferences, in Advances in
Cryptology, CRYPTO ™92, Springer-Verlag, Berlin, LNCS 740 (1993),
471“486.
[32] H. Boender and H.J.J. te Riele, Factoring integers with large prime varia-
tions of the quadratic sieve, Exp. Math. 5 (1996), 257“273.
[33] J.-P. Boly, A. Bossealaers, R. Cramer, R. Michelsen, S. Mjølsnes, F. Muller,
T. Pedersen, B. P¬tzmann, P. de Rooij, B. Schoenmakers, M. Schunter,
L. Vall´e, and M. Waidner, The ESPRIT project CAFE ” High security
e
digital payment systems, in Computer Security, ESORICS ™94 Springer-
Verlag, Berlin, LNCS 875 (1994), 217“230.
[34] D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer-
ican Mathematical Society 46 (1999), 203“213.
[35] D. Boneh, Simpli¬ed OAEP for the RSA and Rabin functions, in Ad-
vances in Cryptology, CRYPTO 2001, Springer-Verlag, Berlin, LNCS
2139 (2001), 275“291.
[36] D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d less than
N 0.292 , IEEE Trans. Inf. Theor. 46 (2000), 1339“1349.

[37] D. Boneh, G. Durfee, and Y. Frankel, An attack on RSA given a fraction
of the private key bits, in Advances in Cryptology, ASIACRYPT 1998,
Springer-Verlag, Berlin, LNCS 1403 (1998), 25“34.

[38] D. Boneh, A. Joux, and P.Q. Nguyen, Why textbook ElGamal and RSA
encryption are insecure, in Advances in Cryptology, ASIACRYPT 2000
(Kyoto), Springer-Verlag, Berlin, LNCS 1976 (2000), 30“43.
[39] D. Boneh and R. Lipton, Algorithms for black-box ¬elds and their ap-
plications to cryptography in Advances in Cryptology, CRYPTO ™96,
Springer-Verlag, Berlin, LNCS 1109 (1996), 283-297.
[40] D. Boneh and H. Shacham, Fast variants of RSA, CryptoBytes 5 (2002),
1“9.
[41] D. Boneh and R. Venkatesan, Breaking RSA may be easier than factoring,
preprint.




© 2003 by CRC Press LLC
252 RSA and Public-Key Cryptography

[42] P. Bonner, Adding cookies to your site, from CNET: Web Building:
http://builder.cnet.com/webbuilding/pages/Programming/Cookies
/?st.bl.pr.10.feat.1140
[43] S. Brands, An e¬cient o¬-line electronic cash system based on the repre-
sentation problem, Report CS-R9323, Centrum voor Wiskunde en Infor-
matica (1993).
[44] S. Brands, Untraceable o¬-line cash in wallets with observers, in Advances
in Cryptology, CRYPTO ™93, Springer-Verlag, Berlin, LNCS 773 (1994),
302“318.

[45] S. Brands, O¬-line cash transfer by smart cards, in Proceedings First
Smart Card Research and Advanced Applications Conference, V.
Cordonnier and J.-J. Quisquater, eds. (1994), 101“117.
[46] J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman, and S.S. Wagsta¬,
Jr., Factorizations of bn ± 1,b = 2, 3, 5, 6, 7, 10, 11, 12 up to High
Powers, Contemp. Math. 22, American Mathematical Society, Providence,
R.I. (1983).
[47] J. Brillhart and J. Selfridge, Some factorizations of 2n ± 1 and related
results, Math. Comp. 21 (1967), 87“96.
[48] J.P. Buhler, H.W. Lenstra, and C. Pomerance, Factoring integers with the
number ¬eld sieve, in The Development of the Number Field Sieve,
A.K. Lenstra and H.W. Lenstra, Jr., eds., LNM, Springer-Verlag, Berlin
1554 (1993), 50“94.

[49] S. Burnett and S. Paine, RSA Security™s O¬cial Guide to Cryptog-
raphy, RSA Press, Osborne/McGraw-Hill, Berkeley, California (2001).
[50] R, Canetti, R. Gennaro, S. Jarecki, and H. Krawczyk, Adaptive security
for threshold cryptosystems, in Advances in Cryptology, CRYPTO ™99,
Springer-Verlag, Berlin, LNCS 1666 (1999), 98“115.

[51] D. Chaum, Blind signatures for untraceable payments, in Advances in
Cryptology, CRYPTO ™82, Plenum Press, New York (1983), 199“203.
[52] D. Chaum, Security without identi¬cation: Transaction systems to make
big brother obsolete, Commun. ACM 28 (1985), 1030“1044.
[53] D. Chaum, Blinding for unanticipated signatures, in Advances in Cryp-
tology, EUROCRYPT ™87, Springer-Verlag, Berlin, LNCS 304 (1988),
227“233.
[54] D. Chaum, Online cash checks, in Advances in Cryptology, EURO-
CRYPT ™89, Springer-Verlag, Berlin, LNCS 434 (1990), 288“293.




© 2003 by CRC Press LLC
Bibliography 253

[55] C.Y. Chen, C.C. Chang, and W.P. Yang, Cryptanalysis of the secret expo-
nent of the RSA scheme, J. Inf. Sci. Eng. 12 (1996), 277“290.
[56] B. Chor and R.L. Rivest, A knapsack-type public-key cryptosystem based
on arithmetic in ¬nite ¬elds, in Advances in Cryptology, CRYPTO ™84,
Springer-Verlag, Berlin, LNCS 196 (1985), 54“65.
[57] B. Chor and R.L. Rivest, A knapsack-type public-key cryptosystem based on
arithmetic in ¬nite ¬elds, IEEE Trans. Inf. Theor. IT-34 (1988), 901“909.
[58] C.C. Cocks, A note on “non-secret” encryption, GCHQ/CESG publication,
November 20 (1973), 1 page.
[59] H. Cohen, A Course in Computational Algebraic Number Theory,
Springer-Verlag, Berlin (1993).

[60] D. Coppersmith, Small solutions to polynomial equations, and low exponent
RSA vulnerabilities, J. Cryptol. 8 (1995), 101“114.

[61] D. Coppersmith, Small solutions to polynomial equations, and low exponent
RSA vulnerabilities, J. Cryptol. 10 (1997), 233“260.
[62] D. Coppersmith, M. Franklin, J. Patarin, and M. Reiter, Low exponent
RSA with related messages, in Advances in Cryptology, EUROCRYPT
™96, Springer-Verlag, Berlin, LNCS 1070 (1996), 1“9.
[63] D. Coppersmith, A. Odlyzko, and R. Schroeppel, Discrete logarithms in
GF (p), Algorithmica 1 (1986), 1“15.
[64] R. Cramer, I. Damg¨rd, and S. Fehr, On the cost of reconstructing a secret,
a
or VSS with optimal reconstruction phase, in Advances in Cryptology,
CRYPTO 2001, Springer-Verlag, Berlin, LNCS 2139 (2001), 503“523.
[65] A.J.C. Cunningham and H.J. Woodall, Factorization of
y “ 1, y = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers (n), Hodg-
n

son, London (1925).
[66] J.A. Davis, D.B. Holdridge, and G.J. Simmons, Status report on factoring
(at Sandia National Labs.), in Advances in Cryptology, EUROCRYPT
™84, Springer-Verlag, Berlin, LNCS 209 (1985), 183“215.
[67] J.M. DeLaurentis, A further weakness in the common modulus protocol for
the RSA cryptoalgorithm, Cryptologia 8 (1984), 253“259.
[68] B. Den Boer, Di¬e-Hellman is as strong as discrete log for certain primes,
in Advances in Cryptology, CRYPTO ™88, Springer-Verlag, Berlin,
LNCS 403 (1990), 530“539.
[69] D.E. Denning and G.M. Sacco, Timestamps in key distribution protocols,
Commun. ACM 24 (1981), 533“536.



© 2003 by CRC Press LLC
254 RSA and Public-Key Cryptography

[70] Y. Desmedt, Simmons™ protocol is not free of subliminal channels, in 9th
Foundations Workshop, IEEE Computer Society, Kenmare, Ireland (1996),
170“175.
[71] Y. Desmedt and M. Yung, Minimal cryptosystems and de¬ning subliminal-
freeness, in Proceedings of the IEEE International Symposium on Informa-
tion Theory (1994), 347.

[72] T. Dierks and C. Allen, The TLS protocol, version 1.0, Internet Request
for Comments, 2246 (January 1999).

[73] W. Di¬e, The ¬rst ten years of public-key cryptography, Proc. IEEE 76
(1988), 560“577.
[74] W. Di¬e and M.E. Hellman, New directions in cryptography, IEEE Trans.
Inf. Theor. 22 (1976), 644“654.
[75] W. Di¬e, P.C. Van Oorschot, and M.J. Weiner, Authentication and au-
thenticated key exchanges, Designs, Codes, Cryptogr. 2 (1992), 107“125.
[76] J.D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36
(1981), 255“260.
[77] B. Dodson and A.K. Lenstra, NFS with four large primes: an explosive
experiment, in Advances in Cryptology, CRYPTO ™95, Springer-Verlag,
Berlin, LNCS 963 (1995), 372“385.
[78] W. van Eck, Electromagnetic radiation from video display units: An eaves-
dropping risk?, Comput. Security 4 (1985), 269“286.
[79] T. ElGamal, A public key cryptosystem and a signature scheme based on
discrete logarithms, in Advances in Cryptology, CRYPTO ™84, Springer-
Verlag, Berlin, LNCS 196 (1985), 10“18.
[80] T. ElGamal, A public key cryptosystem and signature scheme based on
discrete logarithms, IEEE Trans. Inf. Theor. 31 (1985), 469“472.
[81] M. Elkins, MIME security with Pretty Good Privacy, Internet Request for
Comments 2015 (October 1996).

[82] J.H. Ellis, The possibility of secure non-secret digital encryption, GCHQ“
CESG publication, January (1970), 7 pages.
[83] J.H. Ellis, The history of non-secret encryption, GCHQ“CESG publication
(1987), 4 pages.
[84] P. Erd¨s, On the converse of Fermat™s theorem, American Mathematical
o
Monthly 56 (1949), 623“624.
[85] U. Feige, A. Fiat, and A. Shamir, Zero-knowledge proofs of identity, Proc.
19th Annu. ACM Symp. Theor. Comput. (1987), 210“217.


© 2003 by CRC Press LLC
Bibliography 255

[86] U. Feige, A. Fiat, and A. Shamir, Zero-knowledge proofs of identity, J.
Cryptol. 1 (1988), 77“94.
[87] N. Ferguson, Single item o¬-line coins, in Advances in Cryptology,
Eurocrypt ™93, Springer-Verlag, Berlin, LNCS 765 (1994), 318“328.
[88] A. Fiat and A. Shamir, How to prove yourself: Practical solution to identi-
¬cation and signature problems, in Advances in Cryptology, CRYPTO
™86, Springer-Verlag, Berlin, LNCS 263 (1987), 186“194.
[89] FIPS 186, Digital signature standard, Federal Information Processing Stan-
dards Publication 186, U.S. Department of Commerce/N.I.S.T. National
Technical Information Service, Spring¬eld, Virginia (1994).
[90] M.K. Franklin and M.K. Reiter, A linear protocol failure for RSA with
exponent three, Note for CRYPTO ™95 rump session (1995).
[91] E. Fujisaki and T. Okamaoto, Secure integration of asymmetric and sym-
metric encryption schemes, in Advances in Cryptology, CRYPTO ™99,
Springer-Verlag, Berlin, LNCS 1666 (1999), 537“554.
[92] E. Fujisaki, T. Okamoto, D. Pointcheval, and J. Stern, RSA-OAEP is secure
under the RSA assumption, in Advances in Cryptology, CRYPTO 2001,
Springer-Verlag, Berlin, LNCS 2139 (2001), 260“274.

[93] M. Gardiner, A new kind of cipher that would take millions of years to
break, Sci. Am. 237, August (1977), 120“124.
[94] M.R. Garey and D.S. Johnson, Computers and Intractability, W. H.
Freeman, New York, 22nd printing (2000).

[95] C. F. Gauss, Disquisitiones Arithmeticae (English edition), Springer-
Verlag, Berlin (1985).

[96] R. Gennaro, T. Rabin, and H. Krawcyk, RSA-Based undeniable signatures,
J. Cryptol. 13 (2000), 397“416.
[97] M. Girault, Self-certi¬ed public keys, in Advances in Cryptology, EU-
ROCRYPT ™91, Springer-Verlag, Berlin, LNCS 473 (1991), 490“497.
[98] O. Goldreich, Modern Cryptography, Probabilistic Proofs and
Pseudorandomness, Springer, Berlin (1999).
[99] O. Goldreich, Foundations of Cryptography ” Basic Tools, Cam-
bridge University Press, New York (2001).

[100] S. Goldwasser, The search for provably secure cryptosystems, in Cryp-
tology and Computational Number Theory, Proceedings of the 42nd
Symposium in Applied Mathematics 42, American Mathematical Society
(1990), 89“113.



© 2003 by CRC Press LLC
256 RSA and Public-Key Cryptography

[101] S. Goldwasser and J. Kilian, Almost all primes can be quickly certi¬ed,
Proc. 18th Annu. ACM Symp. Theor. Comput. (STOC), Berkeley (1986),
316“329.
[102] J. Gordon, Strong primes are easy to ¬nd, in Advances in Cryptology,
EUROCRYPT ™84, Springer-Verlag, Berlin, LNCS 209 (1985), 216“223.
[103] L.C. Guillou and J.-J. Quisquater, A practical zero-knowledge protocol
¬tted to security microprocessor minimizing both transmission and memory,
in Advances in Cryptology, EUROCRYPT ™88, Springer-Verlag, Berlin,
LNCS 330, (1988), 123“128.
[104] L.C. Guillou and J.-J. Quisquater, A “paradoxical” identity-based signa-
ture scheme resulting from zero-knowledge, in Advances in Cryptology,
CRYPTO ™88, Springer-Verlag, Berlin, LNCS 403 (1990), 216“231.
[105] L.C. Guillou, M. Ugon, and J.-J. Quisquater, The smart card: A stan-
dardized security device dedicated to public cryptology, in Contemporary
Cryptology: The Science of Information Integrity, G.J. Simmons,
ed., IEEE Press, Piscatoway, New Jersey (1992), 561“613.
[106] J. Guttman, Correct cryptographic protocols provide authentication and
con¬dentiality, The EDGE“MITRE™s Advanced Technology Newsletter, 5
(2001), 6“7, 10.
[107] J. Hastad, Solving simultaneous modular equations of low degree, Siam J.
Comput. 17 (1988), 336“341.
[108] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung, Proactive sharing or:
How to cope with perpetual language leakage, in Advances in Cryptology,
CRYPTO ™95, Springer-Verlag, Berlin, LNCS 963 (1995), 339“352.
[109] R. Housley, Cryptographic message syntax, Internet Request for Com-
ments 2630 (June 1999).

[110] R. Housley, W. Ford, W. Polk, and D. Solo, Internet X.509 public key
infrastructure certi¬cate and CRL pro¬le, Internet Request for Comments
2459 (January 1999).

[111] ITU-T Recommendation X.500, The directory ” overview of concepts and
models, ITU, Geneva, Switzerland (1997).
[112] ITU-T Recommendation X.509, Information technology ” open systems
interconnection ” the directory: authentication framework (June 1997).
[113] D.P. Jablon, Strong password-only authenticated key exchange, Computer
Communications Review, ACM SIGCOMM 26 (1996), 5“26.
[114] D. Johnson, The NP-completeness column: an ongoing guide, J. Algo-
rithms 5 (1984), 433“447.



© 2003 by CRC Press LLC
Bibliography 257

[115] A.M. Johnson and P.S. Gemmell, Authenticated key exchange provably
secure against the man-in-the-middle attack, J. Cryptol. 15 (2002), 139“
148.
[116] A. Joux and R. Lercier Discrete logarithms in GF (p), January 19, 2001,
announced on the NMBRTHRY.Mailing.List.
[117] D. Kahn, The Codebreakers, Macmillan, New York (1967).
[118] S. Katzenbeisser, Recent Advances in RSA Cryptography, Kluwer
Academic Publishers, Dordrecht, the Netherlands (2001).
[119] Lord Kelvin, Nineteenth century clouds over the dynamical theory of heat
and light, Philos. Mag. 2 (1901), 1“40.
[120] P. Kocher, Timing attacks on implementations of Di¬e-Hellman, RSA,
DSS, and other systems, in Advances in Cryptology, CRYPTO ™96,
Springer-Verlag, Berlin, LNCS 1109 (1996), 104“113.

[121] A.G. Konheim, Cryptography, a Primer, John Wiley and Sons, New
York (1981).
[122] E. Knudsen, Elliptic scalar multiplication using point halving, in Ad-
vances in Cryptology, ASIACRYPT ™99 (Singapore), Springer-Verlag,
Berlin, LNCS 1716 (1999), 135“149.
[123] D.E. Knuth, The Art of Computer Programming, Volume 2,
Seminumerical Algorithms, Third Edition, Addison-Wesley, Reading,
Massachusetts (1998).
[124] D.E. Knuth, The Art of Computer Programming, Volume 3, Sort-
ing and Searching, Second Edition, Addison-Wesley, Reading, Mas-
sachusetts (1998).
[125] M. Kraitchik, Th´orie des Nombres, Tome II, Gauthiers-Villars, Paris
e
(1926).
[126] M. Kraitchik, Mathematical Recreations, Dover, New York (1953).
[127] E. Krananaskis, Primality and Cryptography, Wiley, New York
(1986).
[128] H. Krawczyk, The order of encryption and authentication for protecting
communications (or: How secure is SSL?), in Advances in Cryptology,
CRYPTO 2001, Springer-Verlag, Berlin, LNCS 2139 (2001) 310“331.
[129] K. Kurosawa, S. Obana, and W. Ogata, t-identi¬able (k, n)-threshold
secret sharing schemes, in Advances in Cryptology, CRYPTO ™95,
Springer-Verlag, Berlin, LNCS 963 (1995), 410“423.




© 2003 by CRC Press LLC
258 RSA and Public-Key Cryptography

[130] B. Lampson, A note on the con¬nement problem, Commun. ACM 16
(1973), 613“615.
[131] P. Lancaster and M. Tismenetsky, The Theory of Matrices, Second
Edition, Academic Press, New York (1985).
[132] S. Landau, Zero-knowledge and the department of defense, Notices Amer.
Math. Soc. 35 (1988), 5“12.
[133] D.H. Lehmer, Selected Papers of D.H. Lehmer, Volumes I“III, D.
McCarthy, ed., The Charles Babbage Research Centre, St. Pierre, Canada
(1981).
[134] D.N. Lehmer, A theorem in the theory of numbers, Bull. Amer. Math. Soc.
14 (1907), 501“502.

[135] E. Lehmer, On the in¬nitude of Fibonacci pseudo-primes, Fibonacci Q. 2
(1964), 229“230.

[136] H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. Math. 126
(1987), 649“673.
[137] H.W. Lenstra, Jr., On the Chor-Rivest knapsack cryptosystem, J. Cryptol.
3 (1991), 149“155.
[138] A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, and J.M. Pollard, The
factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319“
349.
[139] A.K. Lenstra and M.S. Manasse, Factoring by electronic mail, in Ad-
vances in Cryptology, EUROCRYPT ™89, Springer-Verlag, Berlin,
LNCS 434 (1990), 355“371.
[140] A.K. Lenstra and E.R. Verheul, Selecting cryptographic key sizes, J. Cryp-
tol. 14 (2001), 255“293.

[141] R. Lidl and G.L. Mullen, The world™s most interesting class of integral
polynomials, J. Comb. Math. Comb. Comput. 37 (2001), 87“100.
[142] R. Lidl, G.L. Mullen, and G. Turnwald, Dickson Polynomials, Pitman
Monographs and Surveys in Pure Appl. Math. 65, Longman Scienti¬c and
Technical, Essex, England (1993).
[143] L. Lo´asz, An Algorithmic Theory of Number, Graphs, and Con-
v
vexity, SIAM Publications, Budapest (1986).
[144] G. Lowe, Breaking and ¬xing the Needham-Schroeder public key proto-
col using FDR, in Tools and Algorithms for the Construction and
Analysis of Systems, Springer-Verlag, New York, LNCS 1055 (1996),
147“166.



© 2003 by CRC Press LLC
Bibliography 259

[145] J. Manger, A chosen ciphertext attack on RSA optimal asymmetric en-
cryption padding (OAEP) as standardized in PKCS # 1 v2.0, in Advances
in Cryptology, CRYPTO 2001, Springer-Verlag, Berlin, LNCS 2139
(2001), 230“238.
[146] J.L. Massey, Contemporary cryptology: an introduction, in Contempo-
rary Cryptology: The Science of Information Integrity, G.J. Sim-
mons, ed., IEEE Press, Piscatoway, New Jersey (1992), 1“39.
[147] M. Matsui, Linear cryptanalysis method for the DES cipher, in Advances
in Cryptology, EUROCRYPT ™93, Springer-Verlag, Berlin, LNCS 765
(1994), 386“397.
[148] M. Matsui, The ¬rst experimental cryptanalysis of the Data Encryption
Standard, in Advances in Cryptology, CRYPTO ™94, Springer-Verlag,
Berlin, LNCS 839 (1994), 1“11.

[149] U.M. Maurer, Fast generation of secure RSA-moduli with almost maxi-
mal diversity in Advances in Cryptology, EUROCRYPT ™89, Springer-
Verlag, Berlin, LNCS 434 (1990), 636“647.
[150] U.M. Maurer, Towards the equivalence of breaking the Di¬e-Hellman pro-
tocol and computing discrete logarithms, in Advances in Cryptology,
CRYPTO ™94, Springer-Verlag, Berlin, LNCS 839 (1994), 271“281.
[151] U.M Maurer, Fast generation of prime numbers and secure public-key
cryptographic parameters, J. Cryptol. 8 (1995), 123“155.
[152] U.M. Maurer and S. Wolf, Di¬e-Hellman oracles in Advances in Cryp-
tology, CRYPTO ™96, Springer-Verlag, Berlin, LNCS 1109 (1996), 268“
282.
[153] U.M. Maurer and S. Wolf, The relationship between breaking the Di¬e-
Hellman protocol and computing discrete logarithms, SIAM J. Comput. 28
(1999), 1689“1721.
[154] U. Maurer and S. Wolf, The Di¬e-Hellman Protocol, Designs Codes Cryp-
togr., Spec. Iss. Public Key Cryptogr. 19 (2000), 147“171.

[155] B. Mazur, Rational points on modular curves, in Modular Functions of
One Variable V, Springer-Verlag, Berlin, LNM 601 (1977), 107“148.
[156] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Ap-
plied Cryptography, CRC Press, Boca Raton, Florida (1997).
[157] M. Mignotte, How to share a secret, Cryptography, Workshop Proceed-
ings, Springer-Verlag, Berlin, LNCS 149 (1983), 371“375.
[158] G.L. Miller, Riemann™s hypothesis and tests for primality, J. Comput.
Syst. Sci. 13 (1976), 300“317.



© 2003 by CRC Press LLC
260 RSA and Public-Key Cryptography

[159] Z. Mo and J.P. Jones, A new primality test using Lucas sequences, con-
tained within the Ph.D. thesis by Mo completed at the University of Cal-
gary (1995).
[160] R.A. Mollin, ed., Number Theory and Applications, NATO ASI
C265, Kluwer Academic Publishers, Dordrecht, the Netherlands (1989).
[161] R.A. Mollin, ed., Number Theory, Proc. First Conf. of the Canadian
Number Theory Association, Walter de Gruyter, Berlin (1990).
[162] R.A. Mollin, Quadratics, CRC Press, Boca Raton, Florida (1996).
[163] R.A. Mollin, Fundamental Number Theory with Applications,
CRC Press, Boca Raton, Florida (1998).
[164] R.A. Mollin, Algebraic Number Theory, Chapman Hall/CRC Press,
Boca Raton, Florida (1999).
[165] R.A. Mollin, An Introduction to Cryptography, Chapman Hall/CRC
Press, Boca Raton, Florida (2000).
[166] R. Molva, D. Samfat, and G. Tsudik, Authentication of mobile users,
IEEE Network 8 (1994), 26“34.
[167] P.L. Montgomery, Speeding the Pollard and elliptic curve methods of fac-
torization, Math. Comp. 48 (1987), 243“264.
[168] M. Mouly, and M.-B. Pautet, The GSM system for mobile commu-
nications, Cell & Sys., Telecom Publishing, Olympia, Washington (1992).

[169] S. M¨ller, A survey of IND-CCA secure public-key encryption schemes rel-
u
ative to factoring, in Public-Key Cryptography and Computational
Number Theory, K. Alster, J. Urbanowicz, and H.C. Williams, eds., De
Gruyter, Berlin (2001), 181“196.
[170] M. Myers, R. Ankeny, A. Malpani, S. Galperin, and C. Adams, X.509
Internet Public Key Infrastructure On-Line Certi¬cate Status protocol ”
OCSP, Internet Request for Comments 2560 (June 1999).
[171] S. Nasar, A Beautiful Mind, Touchstone, Simon and Schuster, New
York (1998).

[172] National Institute of Standards and Technology, FIPS 140-1, Security
requirements for cryptographic modules (January 11, 1994).
[173] R.M. Needham and M.D. Schroeder, Using encryption for authentication
in large networks of computers, Commun. ACM 21 (1978), 993“999.
[174] R.M. Needham and M.D. Schroeder, Authentication revisited, Operating
Syst. Rev. 21 (1987), 7.




© 2003 by CRC Press LLC
Bibliography 261

[175] A.M. Odlyzko, Discrete logarithms in ¬nite ¬elds and their cryptographic
signi¬cance, in Advances in Cryptology, EUROCRYPT ™84, Springer-
Verlag, Berlin, LNCS 209 (1984), 225“314.
[176] T. Okamoto, Provably secure and practical identi¬cation schemes and cor-
responding signature schemes, in Advances in Cryptology, CRYPTO
™92, Springer-Verlag, Berlin, LNCS 740 (1993), 31“53.

[177] T. Okamoto and K. Ohta, Universal electronic cash, in Advances in
Cryptology, CRYPTO ™91, Springer-Verlag, Berlin, LNCS 576 (1992),
324“337.
[178] P. van Oorschot, A comparison of practical public-key cryptosystems based
on integer factorization and discrete logarithms, in Contemporary Cryp-
tography: The Science of Information Integrity, G. Simmons, ed.,
IEEE Press, Piscatoway, New Jersey (1992), 289“322.

[179] D. Otway and O. Rees, E¬cient and timely mutual authentication, Oper-
ating Syst. Rev. 21 (1987), 8“10.

[180] N. Pippenger, On the evaluation of powers and related problems “ pre-
liminary version, in 17th Annual Symposium on Foundations of Computer
Science, IEEE Computer Society, Long Beach, California (1976), 258“263.
[181] N. Pippenger, The minimum number of edges in graphs with prescribed
paths, Math. Syst. Theor. 12 (1979), 325“346.
[182] N. Pippenger, On the evaluation of powers and monomials, SIAM J. Com-
put. 9 (1980), 230“250.
[183] PKCS1, Public key cryptography standard no. 1 version 2.0, RSA Labs.

[184] H.C. Pocklington, The determination of the prime or composite nature
of large numbers by Fermat™s theorem, Proc. Cambridge Philos. Soc. 18
(1914“1916), 29“30.

[185] S.C. Pohlig and M.E. Hellman, An improved algorithm for computing loga-
rithms in GF (p) and its cryptographic signi¬cance, IEEE Trans. Inf. Theor.
24 (1978), 106“111.

[186] D. Pointcheval, Chosen-ciphertext security for any one-way cryptosystem,
Proc. PKC 2000, LNCS 1751, Springer-Verlag, Berlin (2000), 129“146.
[187] J.M. Pollard, Theorems on factorization and primality testing, Proc. Cam-
bridge Philos. Soc. 76 (1974), 521“528.
[188] C. Pomerance, Analysis and comparison of some integer factorization
algorithms, in Computational Methods in Number Theory, H.W.
Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam,
(1982), 89“139.



© 2003 by CRC Press LLC
262 RSA and Public-Key Cryptography

[189] C. Pomerance, The number ¬eld sieve, Proc. Symp, Appl. Math. 48
(1994), 465“480.
[190] C. Pomerance, J. Selfridge, and S.S. Wagsta¬, Jr., The pseudoprimes to
2.5 · 109 , Math. Comp. 35 (1980), 1003“1026.

[191] C. Pomerance, J.W. Smith, and R. Tuler, A pipeline architecture for fac-
toring large integers with the quadratic sieve algorithm, SIAM J. Comput.
17 (1988), 387“403.
[192] B. Ramsdell, S/MIME version 3 message speci¬cation, Internet Request
for Comments 2633 (June 1999).
[193] E. Rescorla, Di¬e-Hellman key agreement method, Internet Request for
Comments 2631 (June 1999).
[194] P. Ribenboim, Selling primes, Math. Mag. 68 (1995), 175“182.
[195] H. te Riele, W. Lionen, and D. Winter, Factoring with the quadratic sieve
on large vector computers, J. Comput. Appl. Math. 27 (1989), 267“278.
[196] H. Reisel, Prime Numbers and Computer Methods for Factoriza-
tion, Progress in Mathematics 126, Second Edition, Birkh¨user, Boston
a
(1994).
[197] R. Scheidler and H.C. Williams, A public-key cryptosystem utilizing cy-
clotomic ¬elds, Designs Codes Cryptogr. 6 (1995), 117“131.
[198] B. Schneier, Applied Cryptography, Wiley, New York (1994).

[199] C.P. Schnorr, E¬cient signature by smart cards, J. Cryptol. 4 (1991),
161“174.

[200] B. Schoenmakers, An e¬cient electronic payment system withstanding
parallel attacks, Report CS-R9522, Centrum voor Wiskunde en Informat-
ica, March 1995.
[201] P. Seelho¬, Die Au¬‚¨sung grosser Zahlen in ihre Factoren, Z. Math. Phys.
o
31 (1886), 166“172. (French translation in Sphinx-Oedipe 7 (1912), 84“88.)
[202] A. Shamir, How to share a secret, Commun. ACM 22 (1979), 612“613.
[203] A. Shamir, RSA for paranoids, Cryptobytes 1 (Autumn 1995), 1“4.
[204] D. Shanks, Solved and Unsolved Problems in Number Theory,
Chelsea, New York (1985).

[205] C.E. Shannon, Communication theory of secrecy systems, Bell Syst. Tech.
J. 28 (1949), 656“715.




© 2003 by CRC Press LLC
Bibliography 263

[206] Z. Shmuely, Composite Di¬e-Hellman public-key generating systems are
hard to break, Technical Report #356, TECHNION ” Israel Institute of
Technology, Computer Science Dept. (1985).
[207] V. Shoup, OAEP reconsidered, in Advances in Cryptology, CRYPTO
2001, Springer-Verlag, Berlin, LNCS 2139 (2001), 239“259.
[208] V. Shoup and R. Gennaro, Securing threshold cryptosystems against cho-
sen ciphertext attack, J. Cryptol. 15 (2002), 75“96.
[209] G.J. Simmons, Message authentication without secrecy: A secure com-
munications problem uniquely solvable by asymmetric techniques, in IEEE
Electronics and Aerospace Systems Convention, EASCON ™79 Record, Ar-
lington, Virginia (1979), 661“662.
[210] G.J. Simmons, Message authentication without secrecy, in Secure Com-
munications and Asymmetric Cryptosystems, G.J. Simmons, ed.,
AAAS Selected Symposia Series 69, Westview Press, Boulder, Colorado
(1982), 105“139.
[211] G.J. Simmons, Veri¬cation of treaty compliance-revisited, in Proceedings
of the 1983 IEEE Symposium on Security and Privacy, IEEE Computer
Society Press, Oakland, California (1983), 25“27.
[212] G.J. Simmons, A “weak” privacy protocol using the RSA crypto algorithm,
Cryptologia 7 (1983), 180“182.
[213] G.J. Simmons, The prisoner™s problem and the subliminal channel, in Ad-
vances in Cryptology, CRYPTO ™83, Plenum Press, New York (1984),
51“67.
[214] G.J. Simmons, ed., Contemporary Cryptology ” The Science of
Information Integrity, IEEE Press, Piscatoway, New Jersey (1992)
[215] G.J. Simmons, The subliminal channels in the U.S. digital signature al-
gorithm (DSA), in Proceedings of the Third Symposium on: State and
Progress of Research in Cryptography, Rome, Italy (1993), 35“54.
[216] G.J. Simmons, An introduction to the mathematics of trust in security
protocols, in Proceedings: Computer Security Foundations Workshop VI,
IEEE Computer Society Press, Franconia, New Hampshire (1993), 121“127.
[217] G.J. Simmons, Cryptanalysis and protocol failures, Commun. ACM 37
(1994), 56“65.
[218] G.J. Simmons, Subliminal communication is easy using the DSA, in
Advances in Cryptology, EUROCRYPT ™93, Springer-Verlag, Berlin,
LNCS 765 (1994), 218“232.
[219] G.J. Simmons, Subliminal channels: past and present, Euro. Trans.
Telecommun. 5 (1994), 459“473.


© 2003 by CRC Press LLC
264 RSA and Public-Key Cryptography

[220] G.J. Simmons, Protocols that ensure fairness, in Codes and Ciphers, P.G.
Farrrell, ed., Royal Agricultural College, Cirencester, 1993 (1995), 13“15.
[221] G.J. Simmons, The history of subliminal channels, IEEE J. Selected Areas
Commun. 16 (1998), 452“462.
[222] G.J. Simmons, Results concerning bandwidth of subliminal channels, IEEE
J. Selected Areas Commun. 16 (1998), 463“473.
[223] M. Sipser, Introduction to the Theory of Computation, PWS Pub-
lishers (1997).
[224] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J.
Comput. 6 (1977), 84“85. Erratum: A fast Monte-Carlo test for primality,
SIAM J. Comput. 7 (1978), 118.
[225] D.R. Stinson, Cryptography, CRC Press, Boca Raton, Florida (1995).
[226] C. Suetonius Tranquillus, The Lives of the Twelve Caesars, Corner
House, Williamstown, Massachusetts (1978).
[227] E. Teske, Speeding up Pollard™s rho method for computing discrete loga-
rithms, in ANTS-III, Portland, Oregon (June 1998), J.P. Buhler, ed., LNCS
1423 Springer (1998), 541“554.
[228] E. Teske, On random walks for Pollard™s rho method, Math. Comp. 70
(2001), 809“825.
[229] E.C. Tichmarsh, The Theory of the Riemann Zeta Function, Claren-
don Press, Oxford (1951).
[230] Unknown author, Final report on project C43, Bell Telephone Laboratory,
October (1944), p. 23.
[231] S.A. Vanstone and R.J. Zuccherato, Short RSA keys and their generation,
J. Cryptol. 8 (1995), 101“114.
[232] S. Vaudenay, Cryptanalysis of the Chor-Rivest cryptosystem, J. Cryptol.
14 (2001), 87“100.
[233] M. Weiner, Cryptanalysis of short RSA secret exponents, IEEE Trans. Inf.
Theor. 36 (1990), 553“558.
[234] W. Wen, T. Saito, and F. Mizoguchi, Security of public key certi¬cate based
authentication protocols, Proc. PKC ™2000, LNCS 1751, Springer-Verlag,
Berlin (2000), 196“209.
[235] H.C. Williams, Primality testing on a computer, Ars Combinatoria 5
(1978), 127“185.
[236] H.C. Williams, A modi¬cation of the RSA public-key encryption procedure,
IEEE Trans. Inf. Theor. IT-26 (1980), 726“729.


© 2003 by CRC Press LLC
Bibliography 265

[237] H. C. Williams, A p + 1 method of factoring, Math. Comp. 39 (1982),
225“234.
[238] H.C. Williams, Some public-key crypto-functions as intractable as factor-
ization, Cryptologia 9 (1985), 223“237.
´
[239] H.C. Williams, Edouard Lucas and Primality Testing, Canadian
Mathematical Society Series of Monographs and Advanced Texts, Vol. 22,
Wiley-Interscience, New York (1998).
[240] H.C. Williams, Solving the Pell equation, to appear in Millennial Confer-
ence Proc. 3.
[241] H.C. Williams and B. Schmid, Some remarks concerning the M.I.T.
public-key cryptosystem, BIT 19 (1979), 525“538.

[242] M.J. Williamson, Non-secret encryption using a ¬nite ¬eld, GCHQ“CESG
publication, January 21 (1974), 2 pages.

[243] M.J. Williamson, Thoughts on cheaper non-secret encryption, GCHQ“
CESG publication, August 10 (1976), 3 pages.
[244] Working Group 4 International Telecommunication Union, Task Group
8/1, Working document towards new recommendation: Security mecha-
nisms and operating procedures for FPLMTS, version 8, Doc. 8-1/150, Feb.
14 (1995).
[245] S.Y. Yan, Number Theory for Computing, Springer, Berlin (2000).
[246] G. Yuval, How to swindle Rabin, Cryptologia 3 (1979), 187“190.
[247] P. Zimmerman, The O¬cial PGP User™s Guide, MIT Press, Cam-
bridge, Massachusetts, second printing (1995).




© 2003 by CRC Press LLC