2.5 Iteration Attack
Consider a bijective map E : M ! M of a finite set M onto itself and
its inverse D = E 1 (think of E as an encryption function). Then E is
an element of the full symmetric group S(M) that has the (huge) order
#S(M) = (#M)!. Nevertheless this group is finite, thus there is an s 2 N1
with Es = 1M , hence
D = Es 1
.
As a consequence an attacker can compute D from E by su ciently many
iterations. This attack is relevant only for asymmetric ciphers where the
attacker knows E. The only protection against it is to choose the order of
E, the smallest s 1 with Es = 1M , as large as possible.
The Example of RSA
Let M = Z/nZ, then #S(M) = n!, where n itself is a very large integer.
The attacker could compute En! 1, but even the fastest power algorithm
is not fast enough to accomplish this task in this universe. So the attack
doesn’t seem to put RSA into immediate danger.
However, as a closer look reveals, RSA encryption functions are contained
in a significantly smaller subgroup of S(M)—fortunately the attacker
doesn’t know its order. To see this consider the map
: N ! map(M, M), e 7! Ee with Ee(a) = ae
mod n.
Here are some of its properties:
1. For e, f 2 N we have Eef = Ee Ef since aef ⌘ (af )e (mod n) for all
a 2 M. Hence is a homomorphism of the multiplicative semigroup
N.
2. If e ⌘ f (mod (n)), then Ee = Ef : Assume f = e + k (n), then
af = ae+k (n) ⌘ ae (mod n) for all a 2 M.
3. If e mod (n) is invertible, then Ee is bijective: Assume
de ⌘ 1 (mod (n)), then Ed Ee = E1 = 1M . Hence the map
¯ : M (n) ! S(M)
induced by is a group homomorphism.
4. ¯ is injective: For if (e) = Ee = 1M , then ae ⌘ a (mod n) for all
a 2 M, hence ae 1 ⌘ 1 (mod n) for all a 2 Mn, hence (n)|e 1, thus
e ⌘ 1 (mod (n)).
These remarks prove:
23
Proposition 5 The RSA encryption functions Ee form a subgroup
Hn  S(M) that is isomorphic with M (n) and has order '( (n)) and exponent
( (n)).
Of course the order of a single encryption function Ee could be even
much smaller: All we can say is that the cyclic subgroup hei  M (n) has
order s := ord(e) | ( (n)).
This observation raises two problems:
1. How large is ( (n))?
2. Under what conditions is ord(e) = ( (n))? Or at least not significantly
smaller?
Answer to 1 (without proof): “In general” ( (n)) ⇡ n
8 .
If we want to be sure about this we should choose p, q as special primes
p = 2p0 + 1, q = 2q0 + 1 with di↵erent primes p0, q0 3. Then for n = pq we
have
(n) = kgV(2p0
, 2q0
) = 2p0
q0
=
(p 1)(q 1)
2
⇡
n
2
.
If moreover p and q are superspecial primes, that is, p0 = 2p00 + 1 and
q0 = 2q00 + 1 are special primes too, then
( (n)) = 2p00
q00
=
(p 3)(q 3)
8
⇡
n
8
.
By the prime number theorem, see Section 2.1, we may expect that superspecial
primes exist in astronomic quantities.
Answer to 2: in most cases (also without general proof).
Again, if we want to be sure, we should confine our choices to special or
even superspecial primes. We use some elementary results on finite groups,
see Lemmas 21, 22, and 23 of Appendix A.10.
Let p be an odd prime number. In the additive cyclic group Z/2pZ we
consider the subsets:
Ep = {a mod 2p | 0  a < p, a even} {0},
Op = {a mod 2p | 0  a < p, a odd} {p}.
Clearly, Z/2pZ = {0, p} [ Ep [ Op, and
#Ep = #Op = p 1.
The order of an element x 2 Z/2pZ is
ord x =
8
>>>><
>>>>:
1 () x = 0,
2 () x = p,
p () x 2 Ep,
2p () x 2 Op.
24
We transfer this result to an abstract cyclic group Z2p with generating
element g via the isomorphism
⌧ : Z/2pZ ! Z2p, x 7! gx
.
Let Ep = ⌧EP and Op = ⌧OP . Then the result is:
Lemma 2 The order of an element h 2 Z2p is
ord h =
8
>>>><
>>>>:
1 () h = 1,
2 () h = gp,
p () h 2 Ep,
2p () h 2 Op.
Next we study the orders of the elements of the direct product Z2p ⇥Z2q
for two di↵erent odd primes p and q. Applying Lemma 21 we see that the
order of a pair (g, h) for g 2 Z2p and h 2 Z2q is given by the following table:
ord g =
1 2 p 2p
ord h = 1 1 2 p 2p
2 2 2 2p 2p
q q 2q pq 2pq
2q 2q 2q 2pq 2pq
An obvious count yields:
Proposition 6 Let p and q be two di↵erent odd primes. Then the direct
product group Z2p ⇥ Z2q has
(i) 1 element of order 1,
(ii) 3 elements of order 2,
(iii) p 1 elements of order p,
(iv) 3 · (p 1) elements of order 2p,
(v) q 1 elements of order q,
(vi) 3 · (q 1) elements of order 2q,
(vii) (p 1) · (q 1) elements of order pq,
(viii) 3 · (p 1) · (q 1) elements of order 2pq.
25
Again let p be a prime number. Then the multiplicative group Mp =
(Z/pZ)⇥ of the finite field Z/pZ is cyclic of order p 1. Let q be a prime
di↵erent from p and let n = p · q. Then by the Chinese Remainder Theorem
Mn
⇠= Mp ⇥ Mq is (up to isomorphy) the direct product of two cyclic groups
of orders p 1 and q 1. Hence:
Lemma 3 Let n = pq be the product of two di↵erent odd primes p and q.
Then the multiplicative group Mn = (Z/nZ)⇥ of the quotient ring Z/nZ
has order '(n) = (p 1)(q 1) and exponent (n) = lcm(p 1, q 1). In
particular Mn is not cyclic.
The latter statement is due to the common divisor 2 of p 1 and q 1.
We now consider the case where p = 2p0 + 1 and q = 2q0 + 1 are special
primes. Then
'(n) = 4p0
q0
and (n) = 2p0
q0
.
By Proposition 5 the RSA encryption functions for the module n = pq
make up a group Hn isomorphic with M (n). For special primes we therefore
have by Theorem 2 in Appendix A.4:
Proposition 7 Let n = pq be the product of two di↵erent special primes
p = 2p0 + 1 and q = 2q0 + 1. Then the RSA group
Hn
⇠= M (n)
⇠= Zp0 1 ⇥ Zq0 1
is the product of two cyclic groups of orders p0 1 and q0 1.
In order to derive some more easy results we assume that p and q are
superspecial primes, with p0 = 2p00 + 1 and q0 = 2q00 + 1. Then
Hn
⇠= M (n)
⇠= Z2p00 ⇥ Z2q00 ,
and Proposition 6 applies for the primes p00 and q00:
Proposition 8 Let n = pq be the product of two di↵erent superspecial
primes p = 2p0 + 1 and q = 2q0 + 1 with p0 = 2p00 + 1 and q0 = 2q00 + 1. Then
the RSA group Hn consists of
(i) 1 element of order 1,
(ii) 3 elements of order 2,
(iii) p00 1 elements of order p00,
(iv) 3 · (p00 1) elements of order 2p00,
(v) q00 1 elements of order q00,
26
(vi) 3 · (q00 1) elements of order 2q00,
(vii) (p00 1) · (q00 1) elements of order p00q00,
(viii) 3 · (p00 1) · (q00 1) elements of order 2p00q00.
Since 2p00q00 = ( (n)) is the exponent of Hn we see that almost all of its
elements have their orders near the maximum. More precisely the number
of elements of order < 1
2 ( (n)) = p00q00 is
1 + 3 + 4 · (p00
1) + 4 · (q00
1) = 4 · (p00
+ q00
1).
Corollary 1 The number of elements of Hn with order < 1
2 ( (n)) is
p + q 7.
Proof. Note that p00 = (p 3)/4. 3
Thus this number is ⇡ 2·
p
n if p and q—as recommended in Section 2.4—
are chosen near
p
n. Then the proportion of elements of “small” orders is
⇡ 2/
p
n, and this proportion asymptotically tends to 0 with growing values
of n.
As a consequence we resume: With negligeable exceptions s has the order
of magnitude of n/8. The best known general results are in Chapter 23 of
Shparlinski’s book, see the references for these lecture notes.
In addition to Section 2.2 we formulate the task
(F) Finding the order s of the encryption function.
In the sense of complexity theory we have the implication
(F) ! (A)
but maybe not the reverse implication. If the order s is known, then D =
Es 1 and thus d = es 1 are e ciently computable. Finding the order of the
encryption function is at least as di cult as factoring the module.
27