<<

. 35
( 36 .)



>>

2
(s-' = 7, u1 = 2, up = 8, a"' = 22, y"2 = 9, w = 9). d. (6;9,5) yes
(s-' = 9, u i = 10, u2 = 4, a"' = 59, yu2 = 24, z, = 9), (8;8,3) no (s-' = 4,
˜1 = 10, up = 10, a"' = 59, yu2 = 64, w = 2 # 8), (7; 4,7) yes (s-' = 8,
u1 = 1, up = 10, a"' = 25, yU2 = 64, w = 4). e . (10;7,8) yes (s-l = 7,
u1 = 4, uz = 5 , a"' = 15, yU2= 25, z, = 7), (7; 7,3) yes (s-l = 4,u = 6,
1
u = 6, a"' = 62, yU2= 59, w = 7), (8;7,5) no ( - = 9, u1 = 6, u = 8, p
s'
2
a"' = 62, yu2 = 62, w = 3 # 7).
p; transmitted over
5.1. a. d˜ = 17, d˜ = 9, Alice's hand is y,Bob's is
the channel are the numbers (11, 20, 21), ( l l ) , (14, lo), (17). b. d˜ = 19,
d B = 3, Alice's hand is y, Bob's is a; transmitted over the channel are the
numbers (17, 19, 5), (19), (15, 19), (19). c . d A = 7, d s = 15, Alice's
hand is a, Bob's is p; transmitted over the channel are the numbers (11, 7,
lo), (7), (11, 20), (21). d. d A = 5, d˜ = 19, Alice's hand is a,Bob's is p;
transmitted over the channel are the numbers (21, 15, ll), ( l l ) , (10, ll),
(5). e. dA = 3, d B = 9, Alice's hand is a, Bob's is y;transmitted over
the channel are the numbers (19, 14, 17), (19), (21, 15), (15).
5.2. a. h = 103, d = 52, r-l = 24, bank note is (11,58). b. h = 13,
i = 13, r-l = 20, bank note is (99,22). c . fi = 58, d = 74, r-l = 12,
bank note is (55,55). d. h = 37, d = 46, r-l = 8, bank note is (44,ll).
e. h = 49, d = 70, r-' = 4, bank note is (77,42).
Basics of Contemporary Cryptography for IT Practitioners
188


6 1 Only the following points from the list are on the curve: (1,1), (2,1),
..
and (5,8).
[21(2,2) = (3,5), [2l(4,6) = ( W , (1,3) + ( ˜ 4 )= 0,
6.2.
+ (3,2) = (2,5), (3,5) + (5,1) = (3,2).
(2,2) 71
.. a.
b. 5 = 1111110101.
E = 1111001110. E = 0001000110.
C.
d. E = 0101011011. e. B = 0001010001.
a. Pi 0.002, P x 0.006, P M 0.623, P x 0.051, Ps M
2 3 4 0.311,
7.2. x
b. Pi M 0.000, P M 0.009, P3 M 0.000, P M
2 4
P6 0.000,
0.007.
M
P5 P x 0.099. c. P1 M 0.000, P % 0.697, P3 M
6 2
0.892, 0.000,
M
P4 P M 0.299, P W 0.000. d . Pi M 0.003, P M
5 6 2
0.004, 0.000,
X

P3 P X 0.000, P M 0.801, P X 0.160. e.
4 5 6 0.196,
0.036, x
M
P2 M 0.000, P x 0.001, P x 0.000, P x 0.018, Ps M 0.785.
3 4 5
7.3. a. H x 1.16, n x 6.04. b. H M 0.52, n x 2.42. H 0.9,
c. M
n x 3.76. d. H M 1.08, n M 5.08. e. H x 1.16, n x 6.04.
a PI x 0.7 (% = bcucbcucc), P = 0, P3 M 0.3 ( A = acbcacbcc),
2
7.4. .
p4 = 0, P = 0 , P = 0. b. Pi = 0, Pz = 0, P3 = 0, P M 0.21
5 6 4
( = bCCCUCCBC), P5 M 0.20 ( A = dbbCbbCb), P M 0.59 ( A = ambmbc).
a 6
c. Pi = 0, P = 0, P3 = 0, P = 1 ( A = ccbcubccb), P5 = 0, Ps = 0.
2 4
d. Pi = 0 , P = 0 , P x 0.000 (% = acbbbbcbb), P x 1.000
2 3 4
(% = abccccbcc), P = 0, P = 0.
5 6 e. PI = 0 , Pz = 0, P3 x 0.009
(% = bbbcbbbcb), P % 0.970 (% = cccbcccbc), P = 0, P M 0.021
4 5 6
(% = cccacccuc).
Bibliography



Adleman, L. M. (1979). A subexponential algorithm for the discrete logarithm
problem with applications to crypotgraphy, Proc. IEEE 20th Ann. Symp.
on Foundations of Comput. Sci., pp. 55-60.
Agrawal, M., Kayal, N. and Saxena N. (2002). PRIMES is in P, available on-line:
http://vwv.cse.iitk.ac.in/users/manindra.
Aho, A. V., Hopcroft, J. E. and Ulman, J. D. (1976). The Design and Analysis
of Computer Algorithms, Addison-Wesley, Reading MA.
Alexi, W., Chor, B., Goldreich, 0. and Schnorr, C. P. (1988). RSA and Rabin
functions: Certain parts are as hard as the whole, SIAM J. on Comput.,
17,pp. 194-209.
Bellare, M. and Rogaway, P. (2004). Introduction to Modern Cryptography,
http://uuw-cse.ucsd.sdu/users/mihir/crypto-lecnotes.html.
Bently, J. L., Sleator, D. D., Tarjan, R. E. and Wei, V. K. (1986). A locally
adaptive data compression scheme, Comm. ACM, 29, pp. 320-330.
Billingsley, P. (1965). Ergodic Theory and Information, John Wiley & Sons,
New York.
Blahut, R. E. (1987). Principles and Practice of Information Theory, Addison-
Wesley, Reading, MA.
Blake, I., Seroussi, G. and Smart, N. (1999). Elliptic Curves in Cryptography,
Cambridge University Press.
Blum, M. (1986). How to prove a theorem so no one else can claim it, Proc. Int.
Congress of Mathematicians, Berkeley, CA, pp. 1444-1451.
Chaum, D. (1983). Blind signatures for untraceable payments, Advances in Cryp-
tology - Proc. Crypto 8.2, pp. 199-203.
Chaum, D. (1985). Security without identification: transaction systems to make
big brother obsolete, Comm ACM, 28, pp. 1030-1044.
Cormen, T. H., Leiserson, C. E. and Rivest, R. L. (1990). Introduction to Algo-
rithms, MIT Press, Cambridge, MA.
Daemen, J. and Rijmen, V. (2002) The Design of Rzjndael, Springer. (see also
http: / / a r c .nist.gov/CryptoToolkit/aes/rijndael/).
Diffie, W.and Hellman, M. E. (1976). New directions in cryptography, IEEE
%ns. Inform. Theory, 22, pp. 644-654.

189
Basics of Contemporary Cryptography for IT Practitioners
190


ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on
discrete logarithms, I E E E Trans. Inform. Theory, 31,pp. 469-472.
Elias, P. (1987). Interval and recency rank source coding: two on-line adaptive
variable-length schemes, I E E E Trans. Inform. Theory, 33,1 , pp. 3-10.
Feistel, H. (1973). Cryptography and computer privacy, Scientific American, 228,
pp. 15-23.
Feller, W. (1968). A n Introduction to Probability Theory and its Applications,
John Wiley & Sons, New York, 3rd edition.
FIPS 180-1. (1995). Secure Hash Standard, Federal Information Processing Stan-
dards Publication 180-1, U S . Department of Commerce/N.I.S.T., National
Technical Information Service, Springfield, Virginia.
FIPS 186-2. (2000). Digital Signature Standard, Federal Information Processing
Standards Publication 186-2, U.S. Department of Commerce/N.I.S.T., Na-
tional Technical Information Service, Springfield, Virginia.
FIPS 197. (2001) Advanced Encryption Standard, Federal Information Process-
ing Standards Publication 197, U.S. Department of Commerce/N.I.S.T.,
National Technical Information Service, Springfield, Virginia.
Gallager, R. G. (1968). Information Theory and Reliable Communication,
John Wiley & Sons, New York.
Goldreich, O., Micali, S. and Wigderson A. (1987). How to prove all NP state-
ments in zero knowledge and a methodology of cryptographic protocol de-
sign, Advances in Cryptology - C R Y P T 0 86, SpringerVerlag, pp. 171-185.
Goldwasser, S. and Bellare, M. (2001). Lecture Notes on Cryptography,
http://vww-cse.ucsd.edu/users/mihir/crypto-lecnotes.html.
Kahn, D. (1967). The Codebreakers, Macmillan Publishing Company, New York.
Kendall, M. G. and Stuart, A. (1961) The Advanced Theory of Statistics, 2 -
Inference and Relationship, London.
Kerckhoffs, A. (1883). La cryptographie militaire, J. des Sciences Militaires, 9,
pp. 161-191.
Knuth, D. E. (1973). The A r t of Computer Programming, 3 - Sorting and Search-
ing, Addison-Wesley, Reading, MA.
Knuth, D. E. (1981). The A r t of Computer Programming, 2 - Semi-numerical
Algorithms, Addison-Wesley, Reading, MA, 2nd edition.
Koblitz, N. (1987). Elliptic curve cryptosystems, Math. of Comp., 48, pp. 203-
209.
Krichevsky, R. (1993). Universal Compression and Retrival, Kluver Academic
Publishers.
Lenstra, A. K. and Lenstra, H. W., editors. (1993). The Development of the
Number Field Sieve, Springer-Verlag, LNM, 1554.
McEliece, R. J. (1984). The Theory of Information and Coding: A Mathematical
Framework f o r Communication, Cambridge University Press, Cambridge.
Menezes, A. (1993) Elliptic Curve Public Key Cryptosystems, Kluwer Academic
Publishers.
Menezes, A., van Oorschot, P. and Vanstone, S. (1996) Handbook of Applied
Cryptography, CRC Press.
Mercle, R. C. (1979). Secrecy, Authentication, and Public Key Systems, UMI
Bib liogmphy 191


Research Press, Ann Arbor, Michigan.
Miller, V. S. (1986). Use of elliptic curves in cryptography, Advances in cryptology
- CRYPTO™85, LNCS, 218, pp. 417-426.
Montgomery, P. L. (1985). Modular multiplication without trial division, Math.
Comp., 44,pp. 519-521.
Needham, R. M. and Schroeder, M. D. (1978). Using encryption for authentication
in large networks of computers, Comm. ACM, 21,pp. 993-999.
Nisan, N. and Ta-Shma, A. (1999). Extracting randomness: a survey and new
constructions, J. Comp. and System Sci., 58,1, pp. 148-173.
Nisan, N. and Zuckerman, D. (1996). Randomness is linear in space, J. Comp.
and System Sci., 52,1, pp. 43-52.
Papadimitriou, C. H. (1994). Computational Complexity, Addison-Wesley, Read-
ing, MA.
Plumstead, J. B. (1982). Inferring a sequence produced by a linear congruence,
Advances in Cryptology - Proc. Crypto 82, pp. 317-319.
Pohlig, S. C. and Hellman, M. E. (1978). An improved algorithm for comput-
ing logarithms over GF(p) and its cryptographic significance, IEEE Trans.
Inform. Theory, 24,pp. 106-110.
Rivest, R. L., Shamir, A. and Adleman, L. M. (1978). A method for obtaining
digital signatures and public-key cryptosystems, Comm. ACM, 21,pp. 1 2 C
126.
Rivest, R. L., Robshaw, M. J. B., Sidney, R. and Yin, Y. L. (1998) The RC6
rsasecurity .com/rsalabs/.
Block Cipher, h t t p : //m.
Rosen, K. H. (1992). Elementary Number Theory and its Applications, Addison-
Wesley, Reading, MA.
Rukhin, A. et al. (2001). A Statistical Test Suite f o r Random and Pseudorandom
Number Generators f o r Cryptographic Applications, NIST Special Publica-
tion 800-22 (rev. May, 15, 2001).
Ryabko, B. Ya. (1980). Information compression by a book stack, Probl. Inform.
Transmission, 16,4, pp. 16-21.
Ryabko, B. Ya. (1998). The fast enumeration of combinatorial objects, Discrete
Math. and Applications, 10, 2, pp. 101-119.
Ryabko, B. Ya. (2000). Simply realizable ideal cryptographic system, Probl. In-
form. Transmission, 36,1, pp. 90-95.
Ryabko, B. Ya., Stognienko, V. S. and Shokin, Yu. I. (2004). A new test for ran-
domness and its application to some cryptographic problems, J . Statistical
Planning and Inference, 123,2, pp. 365-376.
Ryabko, B. and Fionov, A. (1997). The fast method of randomization, Probl.
Inform. Transmission, 33,3, pp. 3-14.
Ryabko, B. and Fionov, A. (1999a). Efficient homophonic coding, IEEE Trans.
Inform. Theory, 45,6, pp. 2083-2091.
Ryabko, B. and Fionov, A. (1999b) Fast and space-efficient adaptive arithmetic
coding, Cryptography and Coding, Springer, LNCS, 1746,pp. 270-279.
Ryabko, B. and Matchikina, E. (2000). Fast and efficient construction of an unbi-
ased random sequence, IEEE Trans. Inform. Theory, 46,3, pp. 1090-1093.
Ryabko, B. Ya. and Monarev, V. A. (2004). Using information theory approach
Basics of Contemporary Cryptography for IT Practitioners
192


to randomness testing, J . Statistical Planning and Inference, in press.
Ryabko, B. and Pestunov, A. (2004). “Book stack” as a new statistical test for
random numbers, Probl. Inform. Transmission, 40, 1, pp. 66-71.
Schneier, B. (1996). Applied Cryptography, Second Edition: Protocols, Algorthms,
and Source Code in C, John Wiley & Sons, New York.
Schneier, B. (2000). Self-study course in block cipher cryptanalysis, Cryptologia,
24, 1, pp. 18-34.
Schoof, R. (1995). Counting points on elliptic curves over finite fields, J. ThLoom™e
des Nombres de Bordeaux, 7,pp. 219-254.
Shannon, C. E. (1948). A mathematical theory of communication, Bell System
Technical J., 27,pp. 379-423, 623-656.
Shannon, C. E. (1949). Communication theory of secrecy systems, Bell S y s t e m
Technical J., 28,pp. 656-715.
Silverman, J., H. (1986). T h e Arithmetic of Elliptic Curves, Springer-Verlag,
GTM 106.
Vernam, G. S. (1926). Cipher printing telegraph systems for secret wire and
radio telegraphic communications, J. American Inst. Electrical Eng., 5 5 ,
pp. 109-115.
Welsh, D. (1988). Codes and Cryptography, Claredon Press, Oxford.
Author Index



Adleman, L. M. 27, 37, 39, 43 Okamoto, T. 93

Blum, M. 63 Pestunov, A. 175
Plumstead, J. B. 161
Chaum, D. 71 Pohlig, S. C. 14, 92

Daemen, J. 141, 148 Rijmen, V. 141, 148
Rivest, R. L. 27, 43, 144, 163
Diffie, W. 6, 12, 13
Ryabko, B. Ya. 130-132, 173, 175,
ElGamal, T. 24, 46 176
Elias, P. 172
Schoof, R. 102
Schroeder, M. D. 79
Feistel, H. 142
Shamir, A. 22, 27, 43
Fionov, A. N. 130
Shannon, C. E. 5 , 115, 118, 119, 130
Shokin, Yu. I. 175
Hasse, H. 102
Stognienko, V. S. 175
Hellman, M. E. 6, 12-14, 92

<<

. 35
( 36 .)



>>