with A.

able: SSH1 and SSH2, which unfortunately are

As in the Dif¬e-Hellman key agreement scheme,

quite different and incompatible. As for the

if there are no dishonest parties, Alice and Bob

use of cryptographic algorithms, SSH1 supported

will exchange the same key, i.e. k A = k B.

DES (the Data Encryption Standard) Triple-DES,

IDEA, and Blow¬sh, for encryption, while SSH

Yvo Desmedt

supports 3DES, Blow¬sh, Two¬sh, and a few oth-

ers. For authentication, SSH1 supported RSA dig-

Reference

ital signature scheme, while SSH2 supported the

Digital Signature Standard.

[1] Dif¬e, W., P.C. van Oorschot, and M.J. Wiener

(1992). “Authentication and authenticated key ex-

Peter Landrock

changes.” Designs, Codes and Cryptography, 2, 107“

125.

STATION-TO-STATION

PROTOCOL STREAM CIPHER

In a two-party authenticated key exchange the le- A stream cipher is a symmetric cryptosystem (see

gitimate parties can compute a secret key, while at key) which operates with a time-varying trans-

the same time being certain about the authentic- formation on individual plaintext digits. By con-

ity of the parties with whom they exchange a key. trast, block ciphers operate with a ¬xed transfor-

The scheme must, in particular, be secure against mation on large blocks of plaintext digits. More

a man-in-the-middle attack. precisely, in a stream cipher a sequence of plain-

text digits, m0 m1 . . ., is encrypted into a sequence

A popular authenticated version of the Dif¬e“

of ciphertext digits c0 c1 . . . as follows: a pseudo-

Hellman key exchange protocol is the Station-to-

random sequence s0 s1 . . ., called the running-key

Station protocol. It was proposed by Dif¬e-van

Oorschot-Wiener [1]. or the keystream, is produced by a ¬nite state au-

Let g be a suitable ¬nite cyclic group of large tomaton whose initial state is determined by a se-

enough order in which the computational Dif¬e“ cret key. The ith keystream digit only depends on

the secret key and on the (i ’ 1) previous plaintext

Hellman problem is (assumed to be) hard. We as-

sume that q (not necessarily prime) is a multiple digits. Then, the ith ciphertext digit is obtained

of the order of g and publicly known. Let sign A(m) by combining the ith plaintext digit with the ith

indicate the digital signature of the bitstring m keystream digit.

by party A. So, sign A(m) can be veri¬ed using the Stream ciphers are classi¬ed into two types:

public key of A. Let Ek (m) be a conventional en- synchronous stream ciphers and asynchronous

cryption of the bitstring m using the conventional stream ciphers. The most famous stream cipher is

key k. If k is too long, one assumes it is hashed the Vernam cipher, also called one-time pad, that

(see hash function). The corresponding decryption leads to perfect secrecy (the ciphertext gives no

is written as Dk (·). information about the plaintext).

Strong RSA assumption 597

Stream ciphers have several advantages which there is no rationale for requiring strong primes

make them suitable for some applications. Most in RSA. A new factoring method might once again

notably, they are usually faster and have a lower make strong primes desirable for RSA, or on the

hardware complexity than block ciphers. They contrary exploit the properties of strong primes

are also appropriate when buffering is limited, in order to factor more ef¬ciently and thus make

since the digits are individually encrypted and strong primes appear to be dangerous.

decrypted. Moreover, synchronous stream ciphers

Anton Stiglic

are not affected by errorpropagation (see also non-

linear feedback shift register). References

Anne Canteaut

[1] Gordon, J. (1985). “Strong primes are easy to ¬nd.”

Advances in Cryptology”EUROCRYPT™84, Lecture

References Notes in Computer Science, vol. 209, eds. T. Beth,

N. Cot, and I. Ingemarson. Springer-Verlag, Berlin,

[1] Rueppel, R.A. (1986). Analysis and Design of Stream 216“223.

Ciphers. Springer-Verlag, Berlin. [2] Rivest, R.L. and R.D. Silverman (1998). “Are ˜strong™

[2] Vernam, G.S. (1926). “Cipher printing telegraph primes needed for RSA?” Technical Report, RSA

systems for secret wire and radio telegraphic com- Data Security, Inc., Redwood City, CA, USA.

munications.” Journal of the American Institute of [3] Shparlinski, I., J.B. Friedlander, and C. Pomerance

Electrical Engineers, 55, 109“115. (2001). Period of the power generator and small val-

ues of Carmichael™s function. Math. Comp., vol. 70,

1591“1605.

STRONG PRIME

STRONG RSA ASSUMPTION

A strong prime [1] is an integer p such that

r p is a large prime.

r Let 1 < „ ∈ Z be a security parameter. Let N = pq

p ’ 1 has a large prime number factor, denoted

be a product of two random „ -bit primes and let s

r.

r be an element of the group Z— (see also modular

p + 1 has a large prime factor.

r N

r ’ 1 has a large prime factor. arithmetic). The strong-RSA problem is de¬ned as

follows:

The precise quali¬cation of “large” depends on

speci¬c attacks the strong prime is intended to

given (N, s) as input, output a pair a, b ∈ Z

protect against. For a long time, strong primes

such that a b = s mod N and b = ±1.

were believed to be necessary in the cryptosys-

tems based on the RSA problem in order to guard Loosely speaking, the Strong-RSA assumption

states that for a suf¬ciently large „ the strong RSA

against two types of attacks: factoring of the RSA

modulus by the p + 1 and Pollard p ’ 1 factor- problem is intractable.

ing methods, and “cycling” attacks. Rivest and The Strong-RSA assumption was introduced

Silverman [2] published a paper in 1999 argu- by Baric and P¬tzman [2]. The assumption is

ing that strong primes are unnecessary in the used to construct ef¬cient signature schemes

RSA public key encryption system. There are two that are existentially unforgeable under a chosen

points in their argument. First, that the use of message attack without the random oracle model.

strong primes provides no additional protection One such system is described in [4] and an-

against factoring attacks, because the Elliptic other in [3]. The Strong-RSA assumption is also

Curve Method for factoring is about as effective the basis of several ef¬cient group signature

as the p + 1 and the p ’ 1 methods (though none schemes [1].

is particularly likely to succeed for random, large

Dan Boneh

primes) and is not prevented by the strong prime

conditions. Furthermore, the Number Field Sieve

References

can factor RSA modulus with near certainty in less

time than these methods. (See integer factoring

[1] Ateniese, Giuseppe, Jan Camenisch, Marc Joye, and

for a discussion on factoring methods.) Secondly, Gene Tsudik (2000). “A practical and provably se-

they argue that cycling attacks are extremely un- cure coalition-resistant group signature scheme.”

likely to be effective, as long as the primes used Advances in Cryptology”CRYPTO 2000, August,

are large. This has recently been formally proven Lecture Notes in Computer Science, vol. 1880, ed.

in [3]. Thus, in the current state of knowledge, M. Bellare. Springer-Verlag, Berlin, 255“70.

598 Structural cryptanalysis

time T(x) satis¬es

[2] Baric, N. and B. P¬tzman (1997). “Collision-free ac-

cumulators and fail-stop signature schemes without

T(x) < b x

trees.” Proceedings of Eurocrypt, Lecture Notes in

for all suf¬ciently large x. In O-notation, this

Computer Science, vol. 1233, ed. W. Fumy. Springer-

would be written T(x) = 2o(x) or eo(x) .

Verlag, Berlin, 480“494.

[3] Cramer, Ronald and Victor Shoup (2000). “Signa- (In computational complexity, subexponential

ture schemes based on the strong RSA assumption.” security sometimes refers to the related notion

ACM Transactions on Information and System that for all > 0, T(x) < 2x , for all suf¬ciently

Security (ACM TISSEC), 3 (3), 161“185, extended

large x.)

abstract in Proc. 6th ACM Conf. on Computer and

Subexponential-time algorithms occur in cryp-

Communications Security, 1999.

tography in connection with the discrete loga-

[4] Gennaro, Rosario, Shai Halevi, and Tal Rabin

rithm problem and integer factoring. The fastest

(1999). “Secure hash-and-sign signatures without

algorithms known for those problems (i.e., the ones

the random oracle.” Advances in Cryptology”

that grow most slowly as a function of input size)