How to Choose Secret Parameters for RSA-Type Cryptosystems over Elliptic Curves.
Recently, and contrary to the common belief, Rivest and Silverman argued that the use of strong primes is unnecessary in the RSA cryptosystem. This paper analyzes how valid this assertion is for RSA-type cryptosystems over elliptic curves. The analysis is more difficult because the underlying groups are not always cyclic. Previous papers suggested the use of strong primes in order to prevent factoring attacks and cycling attacks. In this paper, we only focus on cycling attacks because for both RSA and its elliptic curve-based analogues, the length of the RSA-modulus n is typically the same. Therefore, a factoring attack will succeed with equal probability against all RSA-type cryptosystems. We also prove that cycling attacks reduce to find fixed points, and derive a factorization algorithm which (most probably) completely breaks RSA-type systems over elliptic curves if a fixed point is found.
Introduction
The theory of elliptic curves has been extensively studied for the last 90 years. In
1985, Koblitz and Miller independently suggested their use in cryptography [9, 19].
After this breakthrough, elliptic curve-based analogues of RSA cryptosystem were
proposed [10, 4].
RSA-type systems belong to the family of public-key cryptosystems. A public-key
cryptosystem is a pair of public encryption function fK and a secret decryption
K indexed by a key K and representing a permutation on a finite set
M of messages. The particularity of such systems is that given the encryption
function fK , it is computationally infeasible to recover f \Gamma1
K . Moreover, it might
be suitable that the encryption function does not let the message unchanged, i.e.
given a message m 2 M, we want that fK (m) 6= m. This is known as the message-
concealing problem [3]. Simmons and Norris [29] exploited this feature for possibly
recovering a plaintext from the only public information. Their attack, the so-
Technical Report No. TI-35/97
Technische Universit?t Darmstadt
November 1997
called cycling attack, relies on the cycle detection of the ciphertext. This was later
generalized by Williams and Schmid [31] (see also [7, 1]).
There are basically two ways to compromise the security of cryptosystems. The
first one is to find protocol failures [20] and the other one is to directly attack the
underpinning crypto-algorithm. The cycling attack and its generalizations fall into
the second category. So, it is important to carefully analyze the significance of
this attack. For RSA, Rivest and Silverman [25] (see also [16]) concluded that the
chance that a cycling attack will succeed is negligible, whatever the form of the
public modulus n. For elliptic curve-based systems, the analysis is more difficult
because the underlying group is not always cyclic. We will actually give some results
valid for groups of any rank, but we will mainly dwell on the security of KMOV
and Demytko's system.
The paper is organized as follows. In Section 2, we review KMOV and Demytko's
system. We extend the message-concealing problem to elliptic curves in Section 3.
Then, we show how this enables to mount a cycling attack on KMOV and De-
mytko's system in Section 4. We explain how the secret factors can be recovered
thanks to the cycling attack in Section 5. Finally, in Section 6, we give some concluding
remarks in order to help the programmer to implement "secure" RSA-type
cryptosystems.
2. Elliptic curves
pq be the product of two large primes p and q, and let two integers a; b
such that gcd(4a 3 curve En (a; b) over the ring Zn is the
set of points (x; y) 2 Zn \Theta Zn satisfying the Weierstra- equation
together with a single element On called the point at infinity.
be an elliptic curve defined over the prime field F p . It is well known
that the chord-and-tangent rule [17, x 2.2] makes E into an Abelian group.
Algebraically, we have:
(i) O p is the identity element, i.e. 8P
(ii) The inverse of
with
\Gammay 2
otherwise.
The points of En (a; b) unfortunately do not form an Abelian group. But writing
e
En (a; b) for the group given by the direct product e
since En (a; b) ae e
En (a; b), we can "add" points of En (a; b) by the chord-and-tangent
rule. For large p and q, the resulting point will be a point of En (a; b) with high
probability [10].
It is useful to introduce some notations. Let
is defined, [k]P will denote P+P+ \Delta \Delta b). The x-coordinate
of P will be denoted by x(P). Moreover, since p 2 (the y-coordinate of P) is not
required to compute the x-coordinate of [k]P, we will write [k] x p 1 for x([k]P).
We can now define an analogue of RSA. The public encryption key e is chosen
relatively prime to
and the secret decryption key d is chosen according to ed j 1 (mod Nn ). To
encrypt a point P 2 En (a; b), one computes the ciphertext [e]P. Then, the
authorized receiver recovers P by computing his secret key d.
The only problem is to imbed messages as points on a given elliptic curve without
the knowledge of the secret factors p and q. A first solution was proposed by
Koyama, Maurer, Okamoto and Vanstone [10]. Another one was later proposed by
2.1. KMOV
KMOV cryptosystem uses a family of supersingular elliptic curves of the form
The main property of this system is that if p and q are both congruent to 2 mod 3,
then whatever the value of parameter b. Therefore, to encrypt
a message chosen according to
and the ciphertext is given by [e]M over the curve En (0; b). The plaintext is
then recovered by
Another possibility is to work with elliptic curves of the form En (a;
and q both congruent to 3 mod 4. The first system based on En (0; b) with p; q j 2
(mod will be referred as Type 1 scheme, and the second one based on En (a;
with systems were extended by
Kuwakado and Koyama to form-free primes [12].
2.2. Demytko's system
Demytko's system uses fixed parameters a and b. It has the particularity to only
make use of the x-coordinate of points of elliptic curves. It relies on the fact that
if a number x is not the x-coordinate of a point on an elliptic curve E p (a; b), then
it will be the x-coordinate of a point of the twisted curve defined as the set
of points (x; y) satisfying
is a fixed quadratic non-residue modulo p, together with the
point at infinity. So, Nn is given by
message m is encrypted as [e] x m. Then, m is recovered from the ciphertext
c by
For efficiency purposes, the original scheme (see [4]) was presented with message-
dependent decryption keys. The length of the decryption key is divided by a factor
of 2, on average. However, in the sequel, we will use the message-independent
description because this simplifies the analysis, and because we are not concerned
with efficiency issues.
3. Concealing-message problem
In [3], Blakley and Borosh showed that there are always at least 9 messages that are
unconcealable (i.e. the ciphertext of a message is exactly the same as the cleartext)
for any RSA cryptosystem. Though this problem is well-known for RSA, nothing
appears in the literature about its elliptic curve-based analogues. Since unconcealed
messages must be avoided, effective criteria are needed for evaluating the concealing
power of these latter systems.
Before analyzing the number of unconcealed messages for elliptic curve-based
systems, we will first give some general group-theoretic results.
G be an Abelian (multiplicatively written) finite group of order #G.
Consider the map G; x 7! x k . Then - k permutes the elements of G if
and only if gcd(k;
Theorem 1 Let G be an Abelian (multiplicatively written) finite group of rank r
whose generators are G; x 7! x k permutes the elements
of G, then - k has exactly
Fix(G;
r
Y
fixed points.
Proof: Write
rg. So,
Each equation has solutions. There are thus
fixed points by the permutation map - k .
Let p and q be distinct primes and let unconcealed message on
RSA, we mean a message m 2 Zn so that m e j m (mod n) for a fixed integer e
latter condition ensures that
the exponentiation by e is a permutation map, or equivalently that RSA encryption
is a permutation of Zn .
pq be the RSA-modulus and let e be the RSA-encryption
key. Then, the number of unconcealed messages for RSA is given by
Proof: Since Z
since 0 is always solution to x e j x (mod p),
Theorem 1 tells that there are (gcd(e \Gamma fixed points in Z p . Moreover,
since by Chinese remaindering, the proof is complete.
Note that since p, q and e are odd integers, there are at least 9 unconcealed
messages for the original RSA system. If we exclude to encrypt 0 and \Sigma1 (that are
always unconcealable messages), there are at least 6 unconcealed messages.
An elliptic curve E p (a; b) over the prime field F p is an Abelian group of rank 1
or 2 and of type (n Theorem 2.12]. Therefore, we can
1. If we call x-fixed point a point
such that, when given an integer k, Theorem 1 becomes:
Theorem be an elliptic curve over the prime field F p . If
permutes exactly
fixed points. Furthermore, - k has exactly
Fix x
x-fixed points, where - 2 is the number of points of order 2.
Proof: The first part follows immediately from Theorem 1.
b). P is a x-fixed point if and only if
we
\Psi , we have
ae
Since O p and points of order 2 are counted twice, we obtain Eq. (11). Indeed,
KMOV Type 1 scheme is based on elliptic curves of the form E
and 3). The underlying group is isomorphic to the cyclic group Z p+1 .
Type 2 scheme uses curves of the form E In
that case, the underlying group is also isomorphic to Z p+1 if a is a quadratic residue
modulo p; and it is isomorphic to Zp+1\Phi Z 2 otherwise. From Eq. (10), for an odd
we see that, for a given KMOV elliptic curve E p (a; b), there are at least 2
fixed points if E p (a; b) is cyclic and at least 4 fixed points otherwise. These points
correspond to the point at infinity together with the points of order 2. Noting that
the encryption key e is always odd for KMOV, and since the point at infinity is not
used to represent messages, there are at least 1, 3 or 9 unconcealed messages on a
given KMOV elliptic curve En (a; b). Consequently, the probability that a random
message is unconcealed can be at least 1=n. This has to be compared with 6=n for
the original RSA.
Demytko's encryption works in a group of the form G (i)
p \Theta G (j)
where G (1)
G (2)
Writing G (i)
, we define
and similarly for G (j)
q . Demytko's system only makes use of the x-coordinate. So,
since the point at infinity is never used for encryption, Theorem 2 indicates that
there are
messages. 2 This
number may be equal to 0, and we cannot give general information on the minimal
number of unconcealed messages in Demytko's system.
For efficiency purposes, the public encryption key e is usually relatively small
(for example, are common choices). In all systems, the
number of unconcealed messages depends on expressions of the form
. Therefore, the maximal number of unconcealed messages
is mainly bounded by (e \Sigma 1) 2 . So, if the encryption key is equal to 2
then the probability that a message is unconcealed is at most - 10 \Gamma144 for a 512-
bit RSA-modulus and - 10 \Gamma299 for a 1024-bit RSA-modulus. Even if the number
of unconcealed messages is small, we will see in the next section how this can be
turned into an active attack.
4. Cycling attack
4.1. Previous results on RSA
be the ciphertext corresponding to message m, where (e; n) is
the public key. If we find an integer k that satisfies the equation
then we can obviously recover the plaintext m by computing
mod n.
Note that we do not have to factor the public modulus n, so this might be a serious
failure for the RSA cryptosystem. This attack, firstly proposed by Simmons and
Norris [29], was later extended by Williams and Schmid [31] (see also [7]) in the
following way. Let P(t) be a polynomial. They showed that if the ciphertext c has
a period such that
for some integer g, then the plaintext m can be recovered.
4.2. Generalizing the cycling attack
We can generalize the results of the previous paragraph to any Abelian finite
group G.
Theorem 3 Let G be an Abelian (multiplicatively written) finite group. Let a
message e be the corresponding ciphertext, where gcd(e;
1. 3 If we find an integer P such that c G, then the plaintext m can be
recovered by computing
is the smallest integer such that m
G. By Lagrange's Theorem, t j #G and since gcd(e;
implies that t j eP and thus t j P . Therefore,
Z such that
letting
and c
We call this theorem the generalized cycling attack. This theorem indicates that
KMOV and Demytko's system are also susceptible to the cycling attack.
Detecting the integer P is equivalent to the problem of finding a polynomial P(t)
and an integer P(g). Moreover, the relation c equivalent
to
If
i denotes the prime decomposition of group order #G and since
(c) divides #G, Eq. (16) can be reduced to
for all primes p i dividing ordG (c).
Here, we must check that these relations hold by picking up a random polynomial
P(t) and a random integer g. This means that the cycling attack depends on
the distribution of such polynomial and of the order of ciphertext c.
Roughly speaking, if the order of G is smooth, we can expect that there are
many elements c 2 G with small order. So, primes p i in Eq. (17) will be small,
and polynomial P will be more easily found. Consequently, it might be desirable
to impose that #G contains at least one large prime in order to make harder the
cycling attack. We will now analyze in more details this assumption for elliptic
curve-based systems.
4.3. Application to elliptic curve systems
As previously mentioned, an elliptic curve E p (a; b; ) over the prime field F p is not
necessarily cyclic, but isomorphic to Zn1 \PhiZ Therefore,
for analyzing the cycling attack over elliptic curves, we have to estimate the number
of points in E p (a; b) of a given order. If is a cyclic group), then
the number of elements of order d is given by the Euler's totient function, namely
OE(d). For the general case, we have:
Proposition be an elliptic curve over the prime field F p . If we
then the number of elements of order d is
equal to
Y
where\Omega d;n2 is the set of primes
is the power of p i which appears in the prime decomposition of n.
Furthermore, given the prime factorization of gcd(#E p (a; can be
computed in probabilistic polynomial time.
Note that
then we take
Proof: The first part of the proposition is proved in Appendix A. The second
part follows from Miller's probabilistic polynomial time algorithm for finding n 1
and n 2 (see [17, x5.4]).
We can now derive a lower bound on the number of elements whose order is
divisible by a large prime factor of the order of E p (a; b).
Proposition be an elliptic curve over the prime field F p . Suppose
that #E p (a; b) is exactly divisible by a prime factor l p . If F div (l p ) denotes the
number of elements of order divisible by l p , then
l p
Proof: See Appendix B.
This proposition indicates that if we randomly pick up an element in E p (a; b), it
has order divisible by l p with probability OE(l p )=l . When l p is large, this
probability is non-negligible (i.e. really "nearly 1").
RSA-type cryptosystems over elliptic curves are constructed on groups of the form
En (a; b), which can be considered as E p (a; b) \Theta E q (a; b) by Chinese remaindering.
In the sequel, we will suppose that #E p (a; b) (resp. #E q (a; b)) contains a large
prime factor l p (resp. l q ). With high probability, a random point
will have order divisible by l p (resp. l q ). Therefore a random
point P on En (a; b) (represented by by Chinese remaindering) will
have order divisible by l p and l q with high probability.
As we discussed in Paragraph 4.2, the cycling attack is reduced to find a polynomial
P and an integer g with c
this attack becomes "Find a polynomial P and an integer g so that [P(g)]C = On
for some ciphertext C 2 En (a; b)". Equivalently, this can be formulated by an expression
of the form of Eq. (17). Since the order of ciphertext C is supposed to be
divisible by l p and l q with high probability, we must have
to mount a successful cycling attack. Williams and Schmid [31]
estimated that these relations are rarely fulfilled except when
k. So, we have thus to take care whether or not
and similarly for prime q. Letting ord l p (e) for the smallest integer satisfying
Eq. (20), k must be a multiple of ord l p (e). Consequently, the cycling attack will be
useless if ord l p (e) is large.
Note 1 In his fast generation algorithm of secure keys, Maurer [15] suggested to verify
that e (l p \Gamma1)=r ip 6j 1 (mod l p) for
p is the prime
decomposition of l p \Gamma 1. This criteria implies that ord l p (e) must be large and the cycling
attack is not applicable. Another method is to impose that l contains a large prime
factor rp . The probability that ord l p (e) is divisible by rp will be then
Proof: Let l
be the prime decomposition
of l p \Gamma 1. The number of elements in Z
l p whose order divisible by rp is given by
rp
rp
rp
l p .
This is known as the strong primes criteria.
Through this section, we have proven some conditions to preclude cycling attacks.
Putting all together, we have:
Theorem 4 The cycling attack does not apply against KMOV if the secret prime
p has the following properties: (i) p+1 has a large prime factor l p , and (ii) ord l p (e)
is large; and similarly for prime q.
Theorem 5 The cycling attack does not apply against Demytko's system if the
elliptic curves over F p have the following properties: (i) #E p (a; b) has a large prime
factor l p and #E p (a; b) has a large prime factor l 0
are large; and similarly for prime q.
5. Factoring the RSA-modulus
5.1. Relation between unconcealed message and cycling attack
For a given ciphertext C 2 En (a; b), the cycling attack detects an integer k satisfying
This is equivalent to the message-concealing problem where the
message is now a ciphertext instead of a cleartext. If E
, from Theorem 2, we know
that there are
Fix(En (a; b); e k
unchanged ciphertexts C via encryption by e k . Moreover, by Eq. (20), [e k
yields l p prime l p dividing #E p (a;
similarly for prime q. So the number of unchanged ciphertexts C is larger than
l p l q .
Suppose that primes p and q were chosen so that both #E p (a; b) and #E q (a; b)
contain a large prime factor l p and l q , respectively. Then, there may be many
ciphertexts C such that [e k and the corresponding cleartexts can be re-
covered. This means that a cycling attack is really effective when applicable. To
prevent this attack, the designer has also to verify that ord l p (e) (resp. ord l q (e)) is
large (see Theorems 4 and 5).
5.2. Factoring by means of fixed points
In Section 4, we explained how the cycling attack can recover a plaintext. Here, we
will show that the knowledge of a unchanged ciphertext enables still more, i.e. to
completely break the system by factoring the RSA-modulus
This can be illustrated by the elliptic curve factoring method (ECM) [13] introduced
by Lenstra. It can basically be described as follows. Suppose that n is the
product of two primes p and q. Consider an elliptic curve En (a; b) over the ring Zn .
Assume that #E p (a; b) or #E q (a; b) is B-smooth. Then define
and choose a random P 2 En (a; b)-note that
[r]P in En (a; b) (and not in E p (a; b) \Theta E q (a; b) because p and q are unknown).
As mentioned in Section 2, some points are not "realizable" because En (a; b) is
not a group. During the computation of [r]P, at step i, three situations can oc-
cur: (i) [r i
and [r i
In cases (i) and (ii), the denominator of - in the chord-and-tangent formulas (see
Eq. (2)) will have a non-trivial factor with n. So n is factored. In case (iii), [r]P
is correctly computed, we obtain of n is found and we then
re-iterate the process with another point P or with other parameters a and b.
Let ord p (P) and ord q (P) be the order of point P in E p (a; b) and E q (a; b), re-
spectively. Let - be a prime. We can write ord p
Hence, if we
know an integer r of the form must
have On in En (a; b). If f p 6= f q , or without loss of generality f
we define r
equivalently
and we find a non-trivial factor of n similarly as in ECM.
The message-concealing problem or the cycling attack is due to the presence of
fixed points P 2 En (a; b) such that
message-concealing problem, and for the cycling attack. The
knowledge of a fixed point P gives [r \Gamma On . We are then in the conditions
of ECM and the RSA-modulus can be factored with some probability as follows.
[Step Choose a prime power factor - of r \Gamma 1, i.e. - t
[Step 3] Compute [r 0 ]P in En (a; b).
If an error occurs (i.e. Eq. (22) is satisfied 4 ), then n is factored. Otherwise,
go to Step 2i; if then go to Step 1.
The next theorem says more about the probability of factoring the RSA-modulus
using one iteration of this method.
Theorem 6 Consider KMOV or Demytko's system. Let E
and - is prime. Let fl - denotes the probability that F p +F q - 2
know a fixed point P 6= On such that [r \Gamma On and if r \Gamma 1 is divisible by -,
then we can factor the RSA-modulus with probability at least fl -
Proof: See in Appendix C.
Assume for example that 0:5 and that we know a point P such that
On . If 2 (which is the most probable case), then our algorithm will find
the secret factors of n with probability at least 15%. Otherwise, we re-iterate the
algorithm with another prime factor - of r \Gamma 1.
5.3. Remark on efficiency
Reconsider the cycling attack [e k n). From Eq. (20), k must be a
multiple of both ord l p (e) and ord l q (e) to apply the attack. However, what we ultimately
need to factor the modulus n is to find an integer r 0 such that, for example,
O q (mod q) (see Eq. (22)); or equivalently, such
that q). This means that a cycling
attack just modulo p (or modulo q) rather than modulo both primes simultaneously
enables to factor n. Therefore, k needs to be just a multiple of ord l p (e) or of
ord l q (e), not of both of them. This results in a higher probability of success.
6. Concluding remarks
In Section 4, we proved that if the conditions of Theorems 4 and 5 are fulfilled,
then cycling attacks are useless for elliptic curve-based RSA systems. This is the
elliptic version of the well-known strong primes criteria. For RSA, Rivest and
Silverman [25] claimed that this criteria is not required. They said:
"Strong primes offer little protection beyond that offered by random primes."
We will now analyze more accurately how valid this assertion is, and if it remains
valid for elliptic curve-based systems. The analogue of Theorems 4 and 5 for original
RSA is:
Theorem 7 Let pq be the RSA modulus and let e be the public encryption
exponent. The cycling attack does not apply against RSA if the secret prime p has
the following properties: (i) has a large prime factor l p , and (ii) l
large prime factor r p (cf Note 1); and similarly for prime q.
A prime p satisfying conditions (i) and (ii) of the previous theorem is said to be
a strong prime. Some authors also recommend that (iii) p + 1 has a large prime
factor. Condition (iii) is required in order to protect against the
algorithm [30].
In their paper, Rivest and Silverman only consider the primes p and q. They did
not take into account the second condition of Theorem 7. 5 Our analysis is based
on a previous work of Knuth and Trabb-Pardo [11] (see also [22, pp. 161-163]),
whom rigorously calculated the distribution of the largest, second largest, . prime
factors of random numbers. Also, they have tabulated:

Table

1. Proportion ae(ff) of (large) numbers N whose largest prime factor is - N 1=ff .
ff 1.5 2.0 2.5 3.0 4.0 5.0 6.0 8.0
We can now more precisely quantify what "large" means in Theorem 7 in order
to prevent cycling attacks. A cycling attack remains to find an integer k such that
(mod n) for some ciphertext c, where e is the public encryption key and
is the RSA-modulus. From k, the plaintext m corresponding to c is then
given by
mod n. However, we noticed in x5.3 that it just suffices to mount
a cycling attack modulo p (instead of modulo n) to factor the RSA-modulus. For
RSA, the secret prime factors are recovered as follows. Suppose that there exists
an integer k such that c e k
will give p; and hence Knowing p and q, the secret key d is computed as
and the plaintext m is then given by
From Eqs (17) and (20), if l p denotes the largest prime factor of must be
(with probability a multiple of ord l p (e) to apply the cycling attack modulo
we thus have k - ord l p (e) with probability at least 1 \Gamma 1=l p . From Knuth and
Trabb-Pardo's results, we can derive how does a typical integer k look. We note that
an average case analysis makes a sense since the distribution of the largest prime
factor, the second largest prime factor, . is monotone. The average size of l p is
similarly, the average size of the largest prime factor r p
of l (Note that we suppose that l behave
like random numbers. This assumption was confirmed by experimental results using
the LiDIA package [14]: over 1 000 000 random 100-bit primes l p , 423 were such that
smooth number, that is, a proportion of 0:000423 - 10 \Gamma3:37 .
This has to be compared with .) The average size of the second
largest prime factor r 0
p of l
divides
(see Note 1), we have
with probability at least (1 \Gamma 1=l . For a
512-bit RSA modulus probability is already greater than
and is greater than modulus. In summary, we have:

Table

2. Lower bound K on a typical value for k
such that c e k
(mod p) for a t-bit RSA modulus
t 512 bits 768 bits 1024 bits
Lower
Albeit very high, the estimation of the bound K (see Table 2) is quite pessimistic;
in practice, k will be much larger than K and a cycling attack (modulo p) will
have thus fewer chances to be effective. Indeed, if we take into account the third
largest prime r 00
p of l p , we have k - r p r 0
with probability at least -
example, for a 1024-bit RSA modulus, we have with probability at least
importantly, we only take into account the largest prime factor
l p of
p be the second largest prime factor of its average size is
. The ciphertext c has its order divisible l p l 0
with probability
at least (1 \Gamma 1=l
. Therefore, from Eq. (17) (see also
Eq. (20)), k is very likely (i.e., with probability
a multiple of lcm(ord l p (e); ord l 0
(e)). The largest prime factor s p of l 0
has an
average size of (l 0
with a probability of
at least (1 \Gamma 1=p 0:210 example, for a 1024-bit RSA
modulus, we have with probability at least 1
Consequently, k is expected to be very large, and a cycling attack will thus have
very little chance to be successful.
Hasse's Theorem [27, Theorem 1.1] indicates that #E p (a; b) 2 [p
and we can thus consider that #E p (a; O(p) and p have the same
bit-size. Therefore, from Theorems 4 and 5, the previous discussion still applies
to elliptic curve-based cryptosystems and the conclusion of Rivest and Silverman
remains valid, i.e. the use of strong primes offers (quasi) no additional security
against cycling attacks.
However, as remarked by Pinch [21], a user might intentionally choose a "weak"
RSA-modulus. Suppose that a user chooses his public RSA-modulus
that a cycling attack is possible. In that case, this user can repudiate a document
by asserting that an intruder has discovered by chance (the probability of a cycling
attack is negligible) the weakness. If the use of strong primes is imposed in
standards [8], such arguments cannot be used for contesting documents in court.
In conclusion, from a mathematical point of view, strong primes are not needed,
but they may be useful for other purposes (e.g., legal issues). On the other hand,
since the generation of strong primes is only just a little bit more time consuming,
there is no reason to not use them.

Acknowledgments

We are grateful to Jean-Marc Couveignes for providing useful comments on a previous
version of this work. We also thank Markus Maurer for teaching us how to
use LiDIA.
Notes
1. OE(n) is the Euler's totient function and denotes the number of positive integers not greater
than and relatively prime to n.
2. Note that this expression slightly differs from Eq. (11). This is because Eq. (11) counts the
number of x-fixed points; here we have to count the number of x-coordinates that are unchanged
by Demytko's encryption.
3. This condition is equivalent to -e in G is a permutation map (see Lemma 1).
4. Or if [r 0 ]P 6= Op (mod p) and [r 0
5. See [25] on p. 17: "Suppose r does not divide ord(e) mod -(N )". Note also the typo, N should
be replaced by -(N).
6. This is the probability that l p divides ord Z
(c) (see Note 1).



--R

Factoring via superencryption.
Security of number theoretic cryptosystems against random attack

A new elliptic curve based analogue of RSA.
Strong RSA keys.
Strong primes are easy to find.
Critical remarks on some public-key cryptosystems
International Organization for Standardization.
Elliptic curve cryptosystems.
New public-key schemes based on elliptic curves over the ring Zn
Analysis of a simple factorization algorithm.
Efficient cryptosystems over elliptic curves based on a product of form-free primes

The LiDIA Group.
Fast generation of secure RSA-moduli with almost maximal diversity
Fast generation of prime numbers and secure public-key cryptographic param- eters
Elliptic curve public key cryptosystems.
Handbook of applied cryptography
Use of elliptic curves in cryptography.
Protocol failures in cryptosystems.
On using Carmichael numbers for public-key encryption systems
Prime Numbers and Computer Methods for Factorization.
Remarks on a proposed cryptanalytic attack on the M.
"Critical remarks on some public-key cryptosystems"
Are 'strong' primes needed for RSA.
A method for obtaining digital signatures and public-key cryptosystems
The Arithmetic of Elliptic Curves.
Fast generation of random
Preliminary comment on the M.

Some remarks concerning the M.
--TR
Strong primes are easy to find
Use of elliptic curves in cryptography
Fast generation of secure RSA-moduli with almost maximal diversity
Prime numbers and computer methods for factorization (2nd ed.)
A new elliptic curve based analogue of RSA
A method for obtaining digital signatures and public-key cryptosystems
Handbook of Applied Cryptography
New Public-Key Schemes Based on Elliptic Curves over the Ring Zn
On Using Carmichael Numbers for Public Key Encryption Systems
RSA-type cryptosystems;strong primes;cycling attacks;elliptic curves