Chapter 1

Computational Number Theory and
Cryptography ∗Preda Mihăilescu and Michael Th. Rassias

Abstract This is a succinct survey of the development of cryptography with accent on the public key age. The paper is written for a general, technically interested reader. We also review some fundamental mathematical ideas of computational number theory, that play an important role in present time cryptography.
Key words Computational number theory, cryptography, elliptic curves over finite
fields, Diffie-Hellman algorithm.
2000 Mathematics Subject Classification 11Y11, 11G05, 11Y16, 11Y40, 68Q17,
68Q25

1.1 Introduction
Cryptography is the collection of methods and approaches for concealing information in communications from the access by unwished or unauthorized parties. A
logical art for dealing with this problem is known from early Antiquity and it developed along the centuries, mostly in the frame in which two parties, say nobleman
and general, or concealed lovers, communicated in written by sending each othermessages which could only be understood when knowing some additional data –secret keys – and the details for the procedure of encrypting and decrypting the messages – algorithm. Algorithms were often assembled from a collection of usefulbasic ideas, known by tradition.
∗

This paper substantially improves and extends the former article of the authors, that appearedin [MR].
Preda Mihăilescu
Mathematisches Institut der Universität Göttingen, Germany, e-mail: preda@uni-math.gwdg.de
Michael Th. Rassias
Department of Mathematics, ETH-Zürich, Rämistrasse 101, 8092 Zürich, Switzerland e-mail:michail.rassias@math.ethz.ch1

2

Preda Mihăilescu and Michael Th. Rassias

1.1.1 Traditional secret key cryptography
Transposing the alphabet of a spoken language into a sequence of numeric codes isalways useful for discussing cryptographic ideas. Suppose thus that the Latin alphabet a, b, . . . , z is encoded in ascending order by the numbers 0, 1, . . . , 24. The ideaof permuting the letters cyclically by a constant σ was purportedly used by Caesarin the Gallic wars – hence the name of Caesar code. For instance, for σ = 3, theword ATHENS becomes DWKHQV. For decryption, use σ = 25 − 3 = 22. One can
improve the security of this code, by using context specific keys, key sequences,and other well defined combination – such variations were investigated in the 16-th
century by the French diplomat Blaise de Vigenère. The purpose was to counter the
obvious weakness of the Caesar code with respect to frequency attacks: provided asufficiently large cipher code, and knowing that letters like e, a, m occur much more
frequently than z, h, q, one can easily determine the value of σ , thus compromising the whole encryption. Since these ideas can in addition be combined with somecommonly known text modifications, the bag of tricks for artisanal cryptography offered sufficient variety for satisfying the needs until the advent of the 20-th century.
In parallel with the development of new, particular algorithms of encryption, theanalysis of methods for discovering both keys and the particularities of an encryption procedure – like for instance the frequency analysis mentioned for the Caesar
cipher – developed itself into the science of cryptanalysis. Today, cryptanalysis andcryptography are regarded as the two complementary aspects of the science of cryptology. While the creation of private codes and keys could be considered to someextent as a playful, even enjoyable undertaking, which requires some rigor though,for preventing countermeasures of the cryptanalyst, the classical encryption has one
more important limitation: the peers need to be in anticipated agreement regarding
both of the encryption algorithm and the keys. This leads to several consequences:
the first is that one would wish the algorithm to be so strong, that it suffices to exchange the keys while keeping the same algorithm over longer periods. The second
is that one needs well trained and faithful couriers for the keys.
In order to illustrate the methods and challenges of classical ciphers, we propose
to the reader to try and decrypt the following small text, which was encrypted bya scheme developed by the 10 year old daughter of the first author starting froma children’s game encryption, found in a book, and which they use for discussing
within a gang of good friends. The cipher text is:
T GGMCIT GW KKNKVCT ZCOKNUKECFGOZCCFCW K
It is obtained by a combination of the ideas discussed above.

1 Computational Number Theory and Cryptography †3

1.1.2 The advent of computing machines ...
In the 20-th century, military confrontations became more devastating, and thepower of data processing with help of machines increased without precedent. However until World War II and even later, the basic scheme for secure communication remained the same: the secret communicators shared some common algorithm,
which could eventually be performed by a machine, and they were using someshared secret key, for the diffusion of which many lives were put in danger. Oneof the most documented episodes of warfare use of cryptography was the German
development of their encryption machine Enigma II on base of a simpler earlier
version Enigma I, which had been a commercial product before the war3 . Little didthey know that this unfortunate combination of economic and military application
had led to the fact that a team of young Polish mathematicians from Poznan were inpossession of a means for breaking Enigma I. When hired by the British authorities,
the work for breaking the enhanced version was, against the German expectation,an achievable one, and the breaking of Enigma had its important consequences forthe outcome of the war. [ENI], [Ka].

1.1.3 ... and of personal computers and networked
communications
The advent of computers brought on the one hand the massive improvement of computational capacities, then, in the early 1970’s, and on the other as the US-army built
the ARPA-net, the advent of networked communications, an ancestor of the Internet.
In front of this progress, cryptography was lead into simplifying the definition of its
object and tasks. Some very useful principles have been established, which stay tohold. First, it was understood that there is little security in the use of proprietary,
secret algorithms – the choice of cryptographers going in the direction of simple,
publicly known and well understood and cryptanalized algorithms. As long as thebag of tricks is known, it can even happen more easily that a flaw escapes in thedesign of a proprietary algorithm. As a consequence the assumed gain of security
obtained from the keeping secret of the cryptographic procedure is counterbalancedby the insecurity stemming from the lack of reliable cryptanalysis. In simple words,
the modern attitude to security is resumed in the paradigm publically known andcryptanalized algorithm and secret keys. As a consequence, the protection of keys
becomes the center of the security concerns and is offered the due attention: thesystem is as secure as the keys are. In addition, the new approach to cryptography
promises that, due to the collective scrutiny of the cryptographic community, in timethe most efficient and reliable algorithms are naturally selected, while weaknesses
and possible attacks eventually show up in the processes. An algorithm is more re3 The development of Enigma I during the early days of mechanical office machine, shows that
there has always existed an important requirement for cryptography also in business.

4

Preda Mihăilescu and Michael Th. Rassias

liable when it has longly resisted public scrutiny by the community, and not when it
is based on sophisticated secret tricks.
We mentioned that in early times of cryptography, secret keys were transported
by couriers which brought their life in danger for this purpose, while even later intimes of telegraphic transmission of keys the problem of building secure channels
for key transmission was a crucial one. In the seventies, the first networked systemof computers became conceivable. It physically realized by the American army, inthe form of the ARPA net, which first connected between 1972 − 1974 a number ofUniversities on the East and West Coast, for research and experimental purposes.
The notion of remote compute-communication became tangible for the users of thenet.
Under these conditions, it became obvious that the old systems for secure key
distribution could not longer satisfy the needs of security for this technological advance and some new ideas were called for, in order to solve the problem in a simple,
time efficient and reliable way.
The idea was provided by the concept of public-key cryptography, which wasborn in Stanford from the joint work of W. Diffie and R. Hellman who studied
public key infrastructures and R. Merkle who studied secret key distribution. Hereis the way Diffie and Hellman presented the problem in [DH], which mentions thejoint work with Merkle: In turn, such applications (fast computers) create a needfor new types of cryptographic systems which minimize the necessity of secure key
distribution channels and supply the equivalent of a written signature.

1.1.4 Public Key Cryptography arises
The idea was remarkably simple and elegant. Its natural properties were strikingly
reflected 30 years later, when it became publicly known and verified, that J. Ellison,an engineer and cryptographer working for MI5’s General Communication HeadQuarters GCHQ, had developed exactly the same concepts and schemes as Diffie,
Hellman and Merkle, yet seven years earlier. The research was only declassified
after the year 2000; it was a matter of academic debate, if a person working for secretservices, outside the academic community should be granted credit for scientificdevelopments. Beyond these it is in any way remarkable that the same ideas could
be developed twice in a totally independent way.
Traditionally, a protected communication was established by using secret key
cryptography. In a wide area communication network, in which numerous peers
could communicate over large distances, the chances for establishing a common secret key prior to communication are low, so there was demand for a procedure which
would allow a pair of peers A and B – Alice and Bob, as cryptographers often use
to name them – to dispose of a shared secret key, without any prior communication,either direct or by means of a parallel, secured channel. Only some public known
data base ∆ , and algorithm could be accepted as premise for achieving the purpose.

1 Computational Number Theory and Cryptography †5

The concept of public key cryptography, introduced by the three authors above
mentioned, is simply described by the following: If X is any peer who wants toengage in secure network communication, he should start by generating a set of data,
which is bundled into his own secret key SX . A subset of this data, bundled in the
public key PX will be made public to all peers he might be wishing to communicate
with – it will be for instance part of the data base ∆ , or it may be transmitted overany unsecured channel. The two keys should enjoy the following two properties:
1. Both keys can be used for encrypting texts according to some algorithm yet todefine.
2. Messages encrypted by SX can be decrypted by PX and vice versa. Moreover,the keys should be sufficiently random: the chances for two peers generating
accidentally the same secret key should be close to zero.
3. It should be computationally unfeasible to derive SX from PX .
For ascertaining the third condition, one usually derives the public key PX fromthe secret one, by using some kind of trap-door function f . Under this term, one
understands an invertible function, such that the value of f is very easy to compute,but the inverse is computable in theory, but infeasible in practice, provided the data issufficiently large. A typical such example is the map f : N× N → N which associates
two primes p, q to their product n = p · q. This can be computed very efficiently evenfor quite large primes. However, the inverse problem, of factoring n is assumed.
There is no proof for the fact that there cannot exist some fast – e.g. polynomialalgorithm, thus one whose run-time is a polynomial in the number m = log2 (n) of
bits of the input number n – for factoring integers. However, the problem is one of
the most intensively researched ones in algorithmic number theory; after decades ofcollective work, the most efficient algorithm for factoring, the Number Field Sieve(NFS) requires the order of
1/3
ecm
binary operations, to be very hard.
On base of the premises 1.– 3., if Alice and Bob want to communicate, then Alicesends to Bob messages encrypted by PB , which she may retrieve from the public key
repository. However, only Bob can decrypt the message, so the communication issecured. On base of this idea, a further useful application emerged: it is often useful
to be able to certify the ownership of some message, to sign the message in a uniqueand non-repudiable way. In this case, secrecy is less of a concern, then ownershipis. The solution consists of associating a short cryptographic hash-value H to themessage, which is encrypted by the secret key SA . Any receiver will then be able toregenerate the hash value on his own, decrypt the encrypted hash with PA , and thencompare the two results. If they match, Bob has a proof that it was Alice who sent
the message.
Within the next 20 years the public key cryptography and the academic paradigmof cryptology spread out and reached probably even most of the banks and diplo-

6

Preda Mihăilescu and Michael Th. Rassias

matic transmissions, which traditionally used to consider the use of private algorithm as a particularly welcome increase of security4 .

1.2 Classical Public Key Cryptosystems
In the next two years after the abstract definition of public key cryptography, twomajor algorithms that implement this idea and are still in use today, were invented5
The first one was using the discrete logarithm problem in the multiplicative groupof finite fields as a trap door. If p is some large prime and g ∈ F×p generates themultiplicative group modulo p and a = gc ∈ F×
p , then it is easy to computef (x) = b = ax , for arbitrary x.
However, to recover x from b, the Discrete Logarithm Problem in finite fields, is acomputationally hard problem – thus adequate for a trap door function. for the factoring problem, there is no proof that no faster algorithms can be found – however,the best one discovered until today has a comparable asymptotic complexity to thenumber field sieve for factoring integers, mentioned above.
Diffie and Hellman proposed an algorithm for exchange of a shared secret overan insecure channel, and is widely known as the Diffie-Hellman key exchange algorithm. It functions as follows: If p and g ∈ F×p are like before – these being publicdata – then Alice and Bob start by choosing some random one time keys AR , BR
which are elements of Z/((q − 1) · Z). Then Alice sends to Bob MA = gAR and receives from Bob MB = gBR . The reader can verify that by using the private data andthe data received, both Alice and Bob may retrieve S = gAR ·BR , which is the datafrom which the common secret key is extracted. However an eavesdropper, who isalways called Eve in cryptography, would only know gAR and gBR but not AR or BR .
The system can be broken by breaking the Discrete Logarithm. But, does the converse also hold? This is not known. The particular, more special problem in whichx y
one should retrieve gxy ∈ F×
p from g , g has received the name DH - Problem, forobvious reasons. More recently, variants of the Diffie - Hellman key exchange havebeen proposed, which can be proved to be equivalent to the DH problem: i.e. they
can be broken if and only if the DH problem is broken. The key exchange algorithm
does not offer the possibility to generate signatures; however J. L. Massey and J.
K. Omura proposed in 1983 a variant based also on the discrete logarithm trap door
function, which allows also public key encryption, and thus signatures.
4 This fact was reflected again in the fact that the producers of cryptographic machinery wereinvolved in customer tailoring algorithms for this purpose. In the late nineties, manufacturers ofcryptographic hardware still had only a precious few customers insisting on the “privilege” ofpurchasing machines which run according to some unique and “secret” algorithm.
5 It is also noteworthy that, after J. Ellis had defined the abstract notion of public key cryptosystems,
in a similar way to Diffie, Hellman and Merkle, the same algorithms were discovered in MI5 too,by C. Crook and M. Williamson, only in the reverse order.

1 Computational Number Theory and Cryptography †7

We should mention that in general public key algorithms are much slower thansecret key encryption. Therefore it is most likely that one would use them for establishing a shared secret key, after which a communication session can be encryptedwith a common agreed secret key algorithm, using the established key. For this purpose the original Diffie - Hellman algorithm is sufficient. Incidentally this two-step
approach to encryption is the core idea in the SSL/TLS protocol, developed between
1992-2002 and which is currently used in all confidential https communications on
the Internet – for instance when you book an electronic flight ticket, or buy a bookfrom Amazon.
The first proper public key encryption algorithm was provided one year later,in 1977, by R. Rivest, A. Shamir and L. Adleman at MIT. Their algorithm, widely
known as RSA after the initials of their names, uses the problem of factoring integers
as a trap door. A secret key consists of SA = {p, q, d}, where p, q are two large primes
satisfying some additional randomness conditions and0 < d < (p − 1)(q − 1),with(d, pq(p − 1)(q − 1)) = 1

is a random number; if e ∈ N is such thated ≡ 1 mod (p − 1)(q − 1),
the public key consists only of PA = (n, e), with n = p · q. In some instances e isa fixed number for the whole system, so d will be determined by the holder of thesecret key using the same defining congruence. With these prerequisites, if M is a
short message it will be identified with a number in Z/(n · Z) and its public key
encryption Me ≡ M e mod n can be computed in the open, but can only be decryptedby Alice, the holder of d, since
M ≡ Med = M ed mod n.
Conversely, if Alice encrypts M with d, then anyone can recover M and upon doing
so will have a proof of Alice having produced the encryption: indeed, only the ownerof the secret key could produce this encryption, which can thus act as a private
signature of Alice.
Despite initial attempts of the NSA to inhibit the publicizing of the ideas of public
key encryption and RSA, these were brought to the public already in 1977 by Martin
Gardner in his widely read column Mathematical Games in the Scientific American
magazine and were eventually published in the communications of the ACM [RSA]:
the way to public key cryptography was open!
In the same year 1978, R. McEliece proposed a somewhat different cryptosystem,
which was inspired from coding theory. The trap door function is drawn in this casefrom general linear codes, a context in which the parameters of a linear code are
specially adapted to the purpose of public key cryptography. The resulting algorithm
has an advantage compared to the number theory based algorithm mentioned above
and some further, based on elliptic curves, that we shall discuss below, since it is8Preda Mihăilescu and Michael Th. Rassias

faster. However, the keys may be as large as 1MB which compares poorly to the
128B required by RSA for a comparable level of security6 .

1.3 Cryptanalysis
In 1978, Hellman and Merkle invented a public key cryptosystem that did not relay
on number theory, but rather on the NP - complete knapsack problem.
The first major success of public key cryptography was that the expectation became true, and the domain of cryptanalysis – concerned with the analysis of possible
attacks against cryptographic schemes – became a flourishing academic domain ofinvestigation. One of the most spectacular successes was due to the developmentof the lattice reduction algorithm by A. Lenstra, H. Lenstra Jr. and L. Lòvasz, the
LLL-algorithm. Given a lattice L ⊂ Zn , there exists a base consisting of the shortest vectors. Classical algorithms for finding such a base are known from the workof Charles Hermite. Only, in the case when the base is presented by an initial generating system of very large vectors, the process is exponential. The algorithm wasdeveloped from techniques used by Lòvasz in integer programming; the idea was touse an approximate Gram-Schmidt-orthogonalisation which provides some close tominimal vectors in L . The advantage is that the algorithm runs in polynomial timeand has therefore a wide variety of applications both in cryptography and in number
theory itself. One of the first applications of LLL was in showing that the keys ofthe knapsack cryptosystem could be cracked in polynomial time: in order to do so,
one had only to solve a particularly simple subfamily of problems belonging to theknapsack family. This result showed the advantage of public academic scrutiny ofcryptographic schemes, since it had only taken five years to reveal the weaknesses of
one of them. But it also blocked the way for applications of the knapsack. Some improved versions have been presented, that could never be attacked – but they nevermade it to public applications.
The most important effect of cryptanalysis was less visible. The community
quickly developed an own language and defined a variety of subtle attack scenarios,
in which the eavesdropper Eve was offered increasing levels of advantages: thus Eve
can simply tap a wire communication, but she might also collect large amounts ofdata signed by Alice, or even induce her into signing a chosen suite of messages.
Thus possible attacks could be investigated for these various levels of disclosure.
The procedure is very fruitful, since the algorithms to which no attack is found,even under the most generous premises for Eve, is for good reasons assumed tooffer reliable security.
Later, the encryption hardware began being regarded as a point of attack, as it
was observed that physical measurements on a chip while it is computing an RSA
encryption, for instance, may reveal some bits of the secret key. Additional measures
6 One compares the security of two fundamentally different algorithms, by estimating the param-

eter sets required, such that breaking the given algorithms by means of the best state of the art
algorithm would require comparably large amounts of time.

1 Computational Number Theory and Cryptography †9were then development to protect from these side channel attacks. This way, welldefined attack scenarios are used for checking the security of various cryptosystems
and -protocols.
The development of cryptography is triggered by the two opposite demands, forefficiency and for security. It occurred more than once, that the wish for efficiency
lead to use some extreme key configurations. These provided particularly efficientarithmetic, thus effective computation of the cryptographic scheme. However, as in
the case of the knapsack problem, the question could have been asked, if by restricting to particular families of the key space, one did not move into a particularinstance of the general, hard problem, to which the trap door function was associated. The question was first answered by the observation that no algorithms are
currently known, that could take advantage of the particular family of keys used.
But eventually, an attack was discovered, which discarded the use of certain keys,
or even whole cryptographic schemes. As an example, it is for instance useful tohave a universal, short public exponent e for the RSA scheme. This had been usedin practice in the late 1980’s. But M. Hagstad and then D. Coppersmith showedthat if e is too small, it is easy to gather sufficiently many messages signed by thesame key SA , and then use simple arithmetic in order to crack that key. Therefore,
the smallest fixed key currently allowed by standards is e = 216 + 1, and this maychange with the growth of computing and storage capacities.
We have already discussed the fact that for the number theoretical public key
systems introduced so far, an efficient attack of the underlying number theoretic
problem (factoring or discrete logarithm) breaks the schemes. Conversely however,
it is not known if general attacks can be found that break the scheme without offering an efficient general solution for the inversion of the trap door function. Suchquestions about provable security became actual in the late nineties. We have already mentioned that by modelling the DH - problem, which is a particular form of
the discrete logarithm, the best results available in this direction were obtained by
U. Maurer [Ma] and V. Shoup and various coauthors e.g. in [CS].

1.3.1 Dickman’s Theorem and the trap door functions
In the thirties of the last century, J. Dickson considered the question of estimating
the largest prime factors of some random integer n. Using heuristic estimates on therepartition of primes, he found for instance that if p|n is the largest prime dividingn, then p = O(nln 2 ). More generally, an integer n > 1 is defined to be y-smooth if
none of its prime factors exceeds y. The functionψ (x, y) = ♯{ 1 ≤ n ≤ x : n is y - smooth }counts the smooth numbers less than x. With these definitions, Dickman also provedthat for all u > 0 there is a real number ρ (u) such that

10

Preda Mihăilescu and Michael Th. Rassiasψ (x, x1/u ) ∼ ρ (u)x.
The function ρ (u) was described in terms of a differential equation, in which u wasfixed for x → ∞.
Half a century later, the gap was filled by Canfield, Erdős and Pomerance [CEP],
who proved that
Theorem 1 ( Canfield, Erdős and Pomerance ). For all real sequences with u → ∞under the constraint u < (1 − ε ) ln x/ ln ln x, one hasψ (x, x1/u ) = xu−u+o(u)(1.1)

As a consequence one concludes that with probability P > 1/2 one out of√
Ln [1/2] := e log(n) log log(n)random integers belonging to the interval (0, n) will be y-smooth, for y = O(L[1/2]).
Bounds of the typec

Ln [c] = elog(n) log log(n)1−c, 0<c<1

are called subexponential for obvious reasons: they grow much faster than any polynomial in m = log(n) but substantially slower than em . All the state of the art, subexponential algorithms for solving either a variant of the discrete logarithm problem,
or for factoring integers, take advantage in some way of this consequence or variants
thereof.
We exemplify here the ideas on the instance of the quadratic sieve method, which
is a classical fast algorithm for factoring integers. It has its origin in the following
simple observation of Fermat: if m is a composite integer, then the congruencex2 ≡ c mod mwill have at least four solutions, and there are x, y such that x 6≡ ±y mod m but
x2 ≡ y2 mod m. Then (x + y, m) is a non trivial factor of m. Theorem
1 helps find√such pairs x, y, as follows: for numbers x(i) in some interval ⌈ n⌉ + i, 0 ≤ i ≤ B,
one computes the remainder7
r(i) = x(i)2 rem m
and retains only those values of x, for which r is a B-smooth number. After gatheringsufficiently many such relations, one may hope that the product of some r(i) is asquare: namely, that there is an index subset J ⊂ [0, B] such that

∏ r(i) = R2 , R ∈ Z.
i∈J

7 In computational algebra, the notation x rem y stands for the unique representative of the equivalence class of x mod y which lays in the interval [0, y).

1 Computational Number Theory and Cryptography †Letting then11

X = ∏ x(i),i∈Jwe obtain the congruence
X 2 ≡ R2 mod m.
If in addition, X 6≡ ±R mod m, which should happen with probability ≥ 1/2, then
(X ± R, m) is a nontrivial factor of m. The method relays on some empirical assumptions on the repartition of factors of r(i): namely, that the distribution of theseresidues is such that one may apply the relation (1.1) for estimating the probability
that one of these numbers is B-smooth. These allow to establish an optimal boundp
B ∼ exp( log(m) log log(m)) = Ln [1/2].
In our case B = L(n; 1/2) and the quadratic sieve runs in time polynomial in B –experience having so far confirmed the underlying heuristical assumptions.
The following nice example is taken√ from the book of R. Crandall and C. Pomerance [CP]: let m = 1649, with 41 = ⌈ m⌉. We find412 ≡ 32 mod m;

422 ≡ 115 mod m;

432 ≡ 200 mod m.

Since 32 · 200 = 25+3 · 52 = 802 , we let R = 80 and
X = 41 · 43 = 422 − 1 ≡ 114 mod m,finding that 1142 ≡ 802 mod m and eventually 17 = (114 − 80, 1649), which is a
non trivial factor.
For the discrete logarithm problem in F×
p , which consists of determining x suchthat gx ≡ b mod p, one uses smooth numbers as follows: Fix a smoothness boundy and let q1 , . . . , qr < y be all the primes up to y. For random values of m, one
computes u = gm rem p and keeps only those values of u which are y-smooth. After
collecting sufficiently many relations, one will then be able to compute the discrete
logarithms li such that qi ≡ gli mod p. Next, one tries random values of k searchingsuch ones which make v = bg−k rem p be a y-smooth number. The precomputed
values li will then help determine x = k + log p (v) from the prime decomposition ofv. This algorithm√ also relies on heuristic assumptions, on base of which the running
time is L p [1/2, 2].
At the end of the 1980’s, John Pollard found a way for applying the idea of thequadratic sieve to integers in number fields rather than Q. The method was first ap9
plied to the factorization of the Fermat number F9 = 22 + 1. In the following years,
it was generalized and improved by a series of mathematicians, starting with A.
Lenstra and M. Manasse. The resulting number field sieve is currently the asymptotically fastest factoring method and it runs in time O(Ln [1/3, c]), for some constantc < 2.
Similar methods are known for the discrete logarithm method: they use number fields in case of larger characteristics, and function fields for small characteris-

12

Preda Mihăilescu and Michael Th. Rassias

tics. Like in the case of factoring, their running time is also O(Ln [1/3, c]). Current
records reach as high as 7 − 800 binary digits for factoring composite of generalform and ∼ 5 − 600 for the discrete logarithm in prime fields. During more than one
decade, the discrete logarithm was hardest in finite fields F pℓ for which ℓ ∼ log(p):these orders of magnitude could not be attacked by either number or function fieldsieves.
Recently A. Joux from INRIA Nancy developed a series of new ideas for improving discrete logarithms in finite non prime extensions. There are several versions
and applications of these ideas. First, they succeed filling in the gap that existed between function field and number field sieve, by providing algorithms in the order of
L p [1/3, c] also for the case of extension fields with ℓ ∼ log(p). They allow to solve
the discrete logarithm problem in quasi- polynomial for field F pℓ when ℓ ∼ p; theresult has been presented at Eurocrypt 2013 and is published in [BGJT]. The ideas
find an other application in discrete logarithm in fields of characteristic two extension degree F2q·k with q a prime and k an integer related to q. Joux also announced avariant of his method to yield an algorithm for discrete logarithms in general fields
of characteristic two, running in Lq [1/4, c], where q is the size of the field [Jo]. This
would be the first known algorithm of this efficiency. The developments in this field
are still quite fluid, but certainly within the following months to few years some important and efficient versions of discrete logarithm algorithms in a variety of fields
will be well described and understood.

1.4 Elliptic curves
The cryptographic schemes discussed so far use multiplicative groups (Z/n · Z)∗
or F×q and related trap door function. Having (computational) access to a larger
family of well understood abelian groups would certainly enlarge the possibilities
for cryptographic and algorithmic applications.
In 1984 René Schoof made the way opening discovery of a polynomial time algorithm for counting the number of points on an elliptic curve over a finite field.
This brought the groups of algebraic geometry in the realm of applications andalgorithms. Within one year, H. W. Lenstra Jr. proposed an important variant of Pollard’s rho-method for factoring, based on elliptic curves: the elliptic curve method
or ECM. Also, V. Miller and N. Koblitz proposed independently the use of elliptic curves for cryptography. The ECM method has a run - time comparable to thequadratic sieve, but it behaves particularly well
√ for numbers m which have somesmall prime factors, i.e. sensibly smaller than m: the run time is namely estimated√to be L p [1/2, 2], where p is the smallest prime dividing m.
We recall that an ordinary elliptic curve over a finite field Fq = F pℓ of characteristic p > 3 is the set of solutions
Eq (a, b) := {P = (X,Y ) : Y 2 = X 3 + aX + b, X,Y ∈ Fq } ⊂ F2q .

1 Computational Number Theory and Cryptography †13

There is an abelian addition ⊕ defined on this curve, which has the point at infinity
O as neutral element. The neutral element can be understood as arising when the
addition law, which is based on rational functions, leads to a division by zero. The
formally correct definition is obtained by embedding the curve in projective space.
The curve is ordinary, if it is not singular and not supersingular, two conditions thatcan be verified in terms of q, b, Fq . Thus
Eq (a, b) = (Eq (a, b), ⊕)becomes an abelian group. The classical theorem of Hasse gives the following
bounds for the size of this finite group:√|Eq (a, b) − q + 1)| < 2 q.

(1.2)

An elliptic curve can be defined in a similar way over the algebraic closure Fq .
Its N-torsion is
E [N] = {P ∈ E : [N]P = O},
where [N]P denotes the N-fold addition of P to itself. The torsion subgroup is –with one exception – a two dimensional free Z/(N · Z)-module, and a vector space,
for prime N. If ζ ∈ Fq is a primitive N−th root of unity, there is a non degeneratebilinear, skew symmetric pairingh·, ·i : E [N] × E [N] → hζ i,(1.3)

the Weil pairing. In particular, if P, Q are linear independent torsion points, thenhP, [x]Qi = (hP, Qi)x ,(1.4)

an identity in the multiplicative group (Fq [ζ ])× .
The idea of the ECM factoring method of Lenstra adapts an older algorithm of
Pollard, which was designed to work in multiplicative groups, to the larger family of
elliptic curves. It can be described briefly as follows: if n is a number to be factored,
one draws random numbers a, b such that a point P = (X,Y ) is known with
Y 2 = X 3 + aX + b, 0 ≤ X,Y < n.
Assume now that n has a prime divisor p such that m := |E p (a, b)| is a B-smooth
integer for some fixed, not too large integer B. If K = B ! then in the process of computing the multiple [K]P by additions and doublings on the curve modulo n one will
most probably encounter a factorization of n: some denominator will be divisible byp (point at infinity!), but not by all the primes dividing n. Lenstra proved that for uniform randomly distributed a, b, the numbers m are close to be uniformly distributedin the Hasse interval (1.2). Theorem 1 then implies that by choosing B = L p [1/2, 1]
random curves, one will find a curve for which m is B-smooth with probability> 1/2. This explains the main steps of the algorithm and of its proof. The interested

14Preda Mihăilescu and Michael Th. Rassias

reader may use Silverman’s [Sil] and Washington’s [Was] textbooks for a detailed
rigorous introduction to elliptic curves and their applications to cryptography.

1.4.1 Counting points
The idea of Schoof is both elegant and important, beyond even the immediate algorithmic and cryptographic applications: it opened a new area of research for practicalalgorithms for counting points on finite abelian varieties. This research area is still
growing, while the main domain of application goes beyond the limits of cryptography, since at least a decade. The algorithms are more and more used for larger
computations related to mathematical questions such as the Birch Swinnerton-Dyer
conjecture, and other properties of L-series. See also [Ra] for an elementary theoretical application of point counting.
Initially, Schoof [Sc1] started from the following simple remark: if
E p (a, b) : Y 2 = X 3 + aX + b
is an elliptic curve defined over the finite field F p , of which one assumes that it isordinary, then Riemann’s conjecture for elliptic curves implies that, in the endomorphism ring of the curve End(E p , F p ) defined over the algebraic closure of F p , theFrobenius verifies the quadratic equation

Φ 2 − t Φ + p = 0.

(1.5)

Since E p is fixed by Φ , we have
|E p (a, b)| = p − t + 1
for the number of points fixed by the Frobenius. Counting the points is thus equivalent to determining the value of the trace of the Frobenius t; since the Hasse inequality (1.2) states that√t < 2 p,it suffices to determine the remainder t rem ℓ for a set of small primes with√
L = ∏ ℓ > 2 p.
Therefore, the core step of the algorithm consists in modeling the ℓ-torsion E p [ℓ]into an algebra
B = F p [X,Y ]/ ψℓ (X), Y 2 − (X 3 + aX + b) ,
P = X + (ψℓ (X)), Y + (Y 2 − (X 3 + aX + b)) ∈ B.
in which ψℓ (X) is the ℓ-division polynomial which has as roots all the x-coordinatesof ℓ-division points. Therefore, any such point enjoys the properties which define the1 Computational Number Theory and Cryptography †15generic ℓ-torsion point P ∈ B. It is then a straightforward computation, to determine
t rem ℓ from the identity
Φ 2 P + pP = t Φ P.
The seminal idea of Schoof, to determine the parameters of the Riemann ζ function from projections in torsion spaces, and thus counting points on varieties
over finite fields was both improved for simple varieties, such as elliptic curves, andextended to more general abelian varieties. In the first case, the primary thing to
do was to reduce the size of the algebra B - which can be done by finding smaller
factors of ψℓ (X) mod p.
The breakthrough in this direction was indicated by Noam Elkies (cf. [Sc2]), whobrought modular forms in the game, thus showing how to find in half of the cases
some factors f (X)|ψℓ (X) of linear degree, compared to the quadratic degree in ℓof the division polynomial. The ℓ-torsion E p [ℓ] ∼= F2ℓ as a vector space; fixing two
linear independent points P, Q ∈ E p [ℓ], we see that G := Gal (B/F p ) acts on thevector space E p [ℓ] by acting on the base P, Q. We obtain herewith a representation
ρ : G → GL2 (Fℓ ), with respect to which ρ (Φ ) verifies the same quadratic equation.
Let δ be the discriminant of the quadratic polynomial in (1.5), which is the sameas the characteristic polynomial of theimage
 of ρ (Φ ) ∈ GL2 (Fℓ ). Then, accordingδto the value of the Legendre symbol ℓ ∈ {1, 0, −1}, the matrix ρ (Φ ) is diagonalizable, has normal upper triangular form or has eigenvalues in Fℓ2 . In the firstcase, there are two eigenpoints P, Q of the Frobenius and the orbit of their x coordinates under multiplication on the curve is galois invariant. We obtain herewith the
eigenpolynomials(ℓ−1)/2

fP (X) =∏ (X − ([k]P)x ) | ψℓ (X),

where

k=1

deg( fP ) = (ℓ − 1)/2,

anddeg(ψℓ ) = (ℓ2 − 1)/2,

together with a new algebra B′ , obtained by replacing ψℓ with fP . For the computation of FP , Elkies considered the function field C[[ j(q)]]. Some classical arguments on Eisenstein series and Γ0 (ℓ)-modular forms, imply that for each j-invariant
jm of an ℓ-isogenous curve to E p – or also, for each zero of the modular equation
Φℓ (X, j(q)) – there is a polynomial f j (X) ∈ C[[ j(q)]][X] which has the x-coordinatesof the kernel of the respective isogeny as zeroes. The polynomials can be constructedin the function field by manipulations of q-expansions and they have the usefulproperty that all the coefficients are algebraic integers. The insight of Elkies was toshow that one can substitute for jm the value of some zero Φℓ (X, j(E p )) mod p andreduce the coefficients of f j (X) modulo p, thus obtaining some eigenpolynomial
corresponding to the value of jm . Indeed, if E is any curve over Q which reduces
to E p at some prime ideal above p, then its j-invariant reduces to the one of E p
and so do the invariants of its ℓ-isogenies. Therefore, if the modular equation has
linear factors jm over F p , by inserting these in the expression for f j (X), upon reduction at the same prime, the coefficients of the polynomial f j map to the onesof some eigenpolynomial. Using improved algorithms for manipulation of series

16

Preda Mihăilescu and Michael Th. Rassias[BMSS], one can compute the eigenpolynomials in time O(log3 (p)), the running
time being dominated by the computation of zeroes of Φℓ (X, j(E p )) mod p. Further
improvements can be achieved by using the galois structure of the resulting algebras[MMS]. The galois theory of finite, commutative algebras has wider applications inalgorithmic context and was generalized in [MV].
For curves defined over finite fields of small characteristic p, it is possible toproject (1.5) in the pN -torsion group. Using different flavors of cohomology combined with Newton iterations, various authors starting with T. Satoh, K. Kedlaya
and A. Lauder developed in this way the most efficient point counting algorithms
for elliptic curves. Some of them are generalized to super elliptic curves, elliptic
surfaces, etc. However, this approach works best only for very small characteristics.

1.4.2 Cryptography
The elliptic curve based cryptographic schemes which have survived scrutiny andbecame part of current standards on public key cryptography are essentially variants of the Diffie-Hellman key exchange scheme and are based on the difficulty ofsolving the discrete logarithm problem: find x such that[x]P = Q,

forP, Q ∈ E p (a, b)

being points on an elliptic curve, such that Q is known to generate a cyclic group ofhigh order. Unlike in finite fields, the discrete logarithm problem on elliptic curves
is not known to allow any sub-exponential time solutions. The best known methods√
have run time O( p), where p is the characteristic of the (prime) field over which
E p is defined. As a consequence, one can work in much smaller groups than in thecase of the multiplicative groups of finite fields, still achieving the same estimatedsecurity of a scheme, with respect to state of the art attacks. This advantage led to a
new wave of interest for elliptic curve cryptography in connection with security ofmobile phones.
The Weil pairing requires certain caution though. One may in principle use theidentity (1.4) in order to reduce the discrete logarithm problem on the elliptic curve
to one in the multiplicative group of the field Fr := Fq [ζ ]. Since discrete logarithms
in multiplicative groups allow for subexponential algorithms, being thus much more
efficient, the size of this extension Fr plays an important role and the reduction
might cause problems when Fr is not too large. The use of the Weil pairing forthe discrete logarithm on supersingular elliptic curves was pointed out for the firsttime by Gerhard Frey. The problem came to light when Frey was asked to estimatea software using these curves – on which a particularly efficient implementationof the group laws is possible – for its security. He showed that for these specificcurves, the Weil pairing reduced the elliptic curve logarithm problem to one in finite
fields of critically small size - Fr = Fqk for k ∈ {2, 3, 6}, thus leading to serious
security problems The idea was taken over by A. J. Menezes, P. C. van Oorschot

1 Computational Number Theory and Cryptography †17

and S. A. Vanstone and is currently known in the literature under the name of MOV
attack. The attack is in general inefficient, but discarded the use of supersingularcurves for cryptographic purpose, for the reasons mentioned above. Interestingly,
more than a decade later, due to the increasing demand for efficient cryptographyusing short bandwidth, in application to securing cell phone communications, thesupersingular curves found a revival. Recently, some research is invested in finding
good combinations of finite fields and supersingular curves, such that on the one
hand time savings can be made in the arithmetic, and on the other hand the field Fr =Fq6 is intractable for the number field sieve discrete logarithm. This example showsthat there still is a certain volatility about development of practical cryptographic
system, which however overlaps the reliable overall results of cryptanalysis.
A further example where efficiency is sought at the critical border line of the
MOV attacks are the so-called Koblitz curves, defined over fields K = Fpℓ of small
characteristic and having a, b ∈ F p . Since p is small, it is of course likely that thefield Fr ⊃ K required for a MOV attack is a not very large extension of K, evenwhen the curves are not supersingular.
In the last years, D. Boneh and A. Joux developed the idea of identity based
cryptography. In order to cope with increasing demand of various cryptographic key,
the idea is to provide the possibility in some limited networks for the user to haveaccess to his secret key essentially by means of his own identity. The most spread
implementation of this idea also uses Weil pairing, and is thus called pairing based
cryptography. The recent developments in discrete logarithms for fields of small
characteristic described above have thus an important impact, requiring significant
increases in the size of the keys used.
Despite of standardization, which made cryptographic developments obsolete in
the Internet, there are thus reasons why research in this particular area is still very
fertile. We recommend the detailed and lively survey of Heß et. al. [HeSSL].

1.5 Key management and biometry
Since the security of a cryptosystem relays in its keys, it is an important task to
manage these keys in a secure and efficient way. In a public-key environment, one
discerns the following essentially distinct aspects:
A. Managing secret keys. Since these are data without meaning for humans, theyshould necessarily be stored on some electronic media, thus leading to the security concern that only the authorized key possessor should have access to the useof these keys.
B. Trusting public keys. We have seen that in the public key setting, Alice needs
to use some public key of Bob. This can either be provided by Bob during thecommunication, or read from a common, public data base. But in both cases,
since the key is obtained over the network, Alice wishes to be certain that the
public key received really belongs to Bob. Otherwise, Eve might for instanceprovide an own key, while convincing Alice that she obtained the public key

18

Preda Mihăilescu and Michael Th. Rassiasof Bob. In this way Eve would be in the position of decrypting messages that
Alice had encrypted in the assumption they should only be accessible to Bob, therightful owner of the secret key belonging to the public one that she received.
There are various solutions for solving both of the above problems. For the first,
keys can be stored on some card device, that needs to be activated by some password. Alternatively, the same principle can be replicated on any variety of securestorage media, including an encrypted hard disk. Alternatively, the user may haveaccess to secure applications that manage keys locally on his behalf. In this case,the activation password will be application-dependent.
For the second problem, the key idea is called certification. Some trusted authority, which has verified the physical identity of Bob matching to his pubic key, will
add a signature on this public key, made with the secret key of the authority. The
signature put by the trusted authority upon Bob’s key is also called a certificate. The
trusted authority’s public key will be accessible in a non forgeable way, so Alicecan verify the signature, thus gaining trust for the fact that Bob’s key is genuine.
In practice, in order to generate a chain of trust reaching from Bob to Alice it may
sometimes be necessary to build up a chain of certificates: trusted authority T1 certifies Bob’s key, T2 certifies the one of T1 , reaching to Tk which is the last authority
the key of which is unconditionally trusted by Alice.

1.5.1 Public Key Infrastructure
The principle is very useful and works well in local networks belonging to an environment which has an own hierarchy of trust which can be naturally mapped tothe certificate hierarchy. Such are for instance large enterprises, administrations andgovernment institutions. Since auxiliary problems of secure key generation, certificate production and verification, secure storage, etc. follow from these key management problem, producing professional solutions to the key management problem oflarge intranets became a market and the typical software solutions are called Public Key Infrastructures (PKI), being systems that allow to implement all the above
mentioned functionalities within the intranet of some institution.
Note that in this case the fact of having a common institutional frame is a major
help, since it allows to distribute the trust according to well defined rules that belong to the institution and are very likely to exist independently of the cryptographic
setting. It is however not always the case that secured communication needs to beestablished within a closed intranet. In that case, although numerous major companies offer the facility of key generation and distribution, thus offering themselves
like some kind of trusted authority for the customer, the level of trust that can be offered to such commercial solutions is rather low and would not suffice for offering
reliable confidentiality.

1 Computational Number Theory and Cryptography †19

1.5.2 The Open System approach
An alternative idea was invented by Paul Zimmerman, who has developed a publicdomain software for secure mail exchange, called Pretty Good Cryptography, andwhich is meanwhile available also as professional software. Zimmerman’s idea oftrust in an open network is strikingly simple: it is likely to assume that the communicating peers – Alice and Bob – can agree upon some commonly trusted instance,
say Tim. In that case Bob can either already hold a certificate signed by Tim, or
one signed by a person that holds a certificate signed by Tim, and so on. If thischain of verifications breaks up, then Bob will be able to provide Alice with a setof certificates that convince her that Tim indirectly trusts Bob. Otherwise, Bob will
have to ask Tim for a certificate which shall be provided a posteriori. In this way
the ring of certificates of each peer grows dynamically, by request and need. While
the trust system here is perfectly non hierarchical and symmetric – now peer has an
unconditional level of trust, some other problems must be taken into consideration.
For instance the fact that the trust chain can be quite unreliable, especially whengrowing too long. Instance A may trust B within a certain frame, and B may trust C,
but at the end A might not have a sufficient level of trust in C at all, and would nothave signed a certificate if directly asked for one.
These elementary concerns have not been mentioned here with the aim of an
exhaustive discussion, but rather in order to raise the awareness about the multiple
facets of the problem of secure key management, while indicating the most important approaches for a solution, with their known advantages and disadvantages.

1.5.3 Passwords and Biometry
We have mentioned that in the case of problem A above, Alice may end up having a
multitude of secret keys distributed through various applications she may work withon a permanent base. And the access to her secret keys will be granted by somepassword, that should sufficiently identify her. This and other contexts in which access is granted based on passwords leads to new issues. First, in order to grant the
password with sufficient security, there should exist both a minimal dynamics – requiring periodical password changes – as a sufficient randomness in the passwords
themselves, which is seldom granted when using passwords that can be memorizedby human. Add to this the expectation that password of the same peer, for different
applications or environments should differ – so that the compromising of one password does not put in danger the whole range of domains accessed by Alice. We seethat the access control by means of passwords poses problems itself.
The identification of persons by means of their physical body or dynamics –called biometric recognition – is a specialty that grew from forensic needs developing itself in the computer era into a self contained branch of computer science at theintersection of image processing, pattern recognition and security. During the first
decades the first two prevailing, leading to gradually improved algorithms which

20

Preda Mihăilescu and Michael Th. Rassias

allows for some satisfactorily recognition and identification. Whether the biometryof concern is provided by fingerprints, iris or face traits, voice or writing patterns,
biometric recognition has always the following specific characteristics:
a. Identification is a stochastic process and not a deterministic one, as for instancein the case of a password verification by means of some one-way function. Since
the biometrics of a person are sampled at two distinct places in time and space
they will not be identical. Due to this and a series of additional factors of incertitude introduced by the physical and computer- processing, identification will
always be subject to error. The standard way to measure these average errors isby overlapping the two possible error sources: false accept, when another person
is falsely accepted for Alice and false reject when Alice’s identity is not acceptedon base of her biometry and she is rejected. The equal error rate (EER) is the optimal performance of a system in which the two error rates are identical.
b. Unless the data caption system has a reliable method for distinguishing live, natural biometrics from artificial counterfacts, impersonation attacks are possible.
c. Biometrics are unique, so a biometric trait once compromised for a certain typeof application, is irreplaceable and of ulterior use of that biometrics has lost its
security.
Despite of these quite restrictive conditions of use biometric identification has theimportant advantage of commodity: it can make the necessity of multiple, dynamic
passwords obsolete. As a consequence, biometry is already in use for access control
applications of low security sensitiveness: access to lounges, clubs, hotel rooms or
as replacement for visitor’s cards. It can also replace the login password for personal computers. When it comes to security applications, neither the potential uses
nor the attacks are so well delimited and classified as is the case in cryptography.
Consequently the security claims one encounters in the vast literature of the field
do not offer the reliability expected from the context of cryptography. One should
therefore recall as a rule of thumb the fact that the probability of a successful attack
against a biometric system is quite well approximated by the EER of the system.
Since EER of one in a million are seldom – being claimed for some systems usingiris recognition, it can be seen that biometric identification is practical and comfortable, but yet not acceptable in conjunction with cryptographic applications. The useof multiple biometrics – including multifinger recognition is therefore an area ofactive research, in which one of the subtle issues to consider is the fact that it should
not be possible to uncouple the individual biometrics.

1.6 Quantum technology and other cryptosystems
The main intensively used public key cryptography methods relay on the number
theoretic problems described above. There have been numerous interesting attempts
to use the large list of NP complete problems in order to derive some trap door
function – the knapsack problem is only one of the most famous ones. We can1 Computational Number Theory and Cryptography †21

hardly go into the detail necessary in order to pay justice both to the interest of theattempts and the reasons for their failure or restricted use.
Before discussing below several alternative cryptosystems which survived thescrutiny of cryptananlyst and are still discussed as possible alternatives, we turnhere our attention to the contribution of physics

1.6.1 The advent of quantum theory
Since the early 1980’s the Canadian mathematicians G. Brassard and C. Crépeausuggested the use of quantum effects for security applications: the simple idea wasthat Eve could not tap a quantum communication wire, without destroying the information content transmitted, so security would be provided by a self-destruction
mechanism introduced by quantum mechanics in the confidential information transmitted. The physical and cryptographical aspects of the idea have been in active
research ever since. Unlike the mathematical systems already described, or also
others that follow, which can be conceived and analyzed on paper, after which theirpractical realization reduces to a quite simple task of programming, the difficulties
encountered in this case were and remain of physical nature. In the first decadeof this century, several practical implementations of quantum 8 cryptography havebeen announced, reaching over distances of up to 100 km. It is thus the distance andthe stability of quantum transmission via fiber-optics which is the bottle neck forthis system.
In the nineties of the last century, various ingenious experiments and ideas foralternative computing infrastructures were imagined or even tested. One may mention along these lines, L. Adleman’s – one of the inventors of RSA – experiments
for computing with bacteria9 . Perhaps the most persisting future projection in thiscontext is the concept of quantum computing; in this case there is a physical idea
behind, which is stable enough in order to lead to formal mathematical models ofcomputations that might be performed on quantum computers; one can use for astart the short introduction given in [ENI]. Using existing models of quantum computers, mathematicians have been developing since more than a decade algorithms
that run according to the given model. It is for instance known that quantum computers can invert all the trap door functions using in the cryptographic schemes
described above, in polynomial time. Developing models for quantum computing is
an on-going area of intensive research activity in which some of the most eminent
theoretical mathematicians and physicists find appealing questions. For instance, theFields medalist Michael H. Freedman leads the Q - Section of Microsoft where heapplies topological methods to quantum computation (cf. [BFLW], [Fre], [FKW],
8 The reader should not confuse quantum cryptography with quantum computing, where quantum
effects are wished to help computations, not only secure information transmission: the physicalchallenges are even larger in the latter case.
9 The idea showed to be in principle feasible, but never reached more than the representation of thedecimal digits on such “computers”

22

Preda Mihăilescu and Michael Th. Rassias[FKLW], [FLW], [FLW2]).
The quantum computers information unit is a qubit; unlike a bit, a qubit can,simply speaking, carry any superposition of the states 0 and 1. The calculation on aquantum computer with n qubits ends with measurement of all the states, collapsingeach qubit into one of the two pure states. It is the fact that computations happen
in a state of superposition of all quantum states which leads to the distinct superior
capacities of quantum computers. Somehow similar to the case of quantum cryptography, there is a major physical problem in the realization of quantum computers,
and that is realizing stable qubits, stability being with respect to the influence of theenvironment and in particular other qubits. There persistent announcements of small
progress in the technology of quantum computing, keeping the hope alive that one
might live the day when first experimental quantum computers carrying more than
3 − 4 qubits will be routinely available. For instance, in order to factor an RSA key
of the currently standard length of 1024 bits, a quantum computer should have inthe order of magnitude of 1024 qubits. With this prerequisite however, the number
would be factored within milliseconds.

1.6.2 Alternative cryptosystems
Public key cryptography is sensibly slower than secret key encryption, by a factor ofroughly 1000, as a thumb rule. This lead to the wish to design some fast asymmetricschemes that does not use the kind of arithmetics which are the bottleneck for the
DH and RSA systems.
A successful solution in this respect was invented by three number theorists:
J. Hoffstein, J. Pipher and J.H. Silverman [HPS]; they designed the cryptosystem
NTRU (Number Theorists are Us), which uses arithmetic in a ring of truncated polynomials, such that decryption - the slower operation - can be done in O(n log(n))
rather than O(n2 log(n)) or more operations, as is the case for RSA. Here, the constant n is roughly the key size. In the case of NTRU, this is slightly larger for comparable security; for instance a comparable security to the one provided by RSA
keys of 1024 bits may require NTRU bits of 4000 bits. This key increase is affordable, for the performance advantage gained. The security of the system is based on
the problem of finding shortest vectors in large lattices. While the best methods forsolving this problem continuously improve, this fact can be easily compensated for,by accordingly small increases of the key sizes. The system NTRU has been developed a lot during the last 15 years and was accepted five years ago also as an IEEE
standard.
Recently, Dan Bernstein gave a new revival to McElieces algorithms, by developing a variant which is technically improved for efficiency and uses, among others,some algorithms for polynomial simultaneous evaluation and interpolation, whichdeveloped in part after the original invention of the cryptosystem. Bernstein refers
to his variant as Mcbits [BCS] and uses the argument that unlike the number theoret-1 Computational Number Theory and Cryptography †23

ical cryptosystems, this scheme is resistant to the state of the art models of quantum
computing. One may of course argue that the day when quantum computers become routinely available, it should be expectable that quantum encryption is available too, thus making mathematical cryptography somehow obsolete. The practicalbottleneck of Mcbits in present days is the size of the keys, with ranges to several
megabytes. It is otherwise an efficient algorithm which can be taken into consideration in environments in which communicating large keys is less of a bottle neck thatthe computation time for encryption/decryption.
A further family of interesting public key schemes uses non commutative groups– such as for instance braid groups, (e.g. cf. [MSU]). Their developers make also apoint out of the fact that the scheme is resistant to quantum computing.

1.7 Conclusion
Cryptography was born in early ages as a skill of mental combinations put at theservice of privacy and military protection. It developed along time into a highly
mathematized discipline, which unites the science of concealing with the analysis
of attacks into one single unit, cryptorology. While the last decades of research andthe development of computers have offered widely satisfactorily methods for solving the elementary needs of security, it seems that the prognoses for the future are
more captivated by the advent of physical solutions offered by quantum mechanics
both to the cryptanalysis of the most widely spread public key schemes but also,
constructively, for the implementation of new, purely physical cryptosystems.
Acknowledgments. We would like to express our thanks to Professor Joseph Silverman for his useful remarks on the manuscript.

References[BGJT] R. Bărbulescu, P. Gaudry, A. Joux, É. Thomé, A quasi-polynomial algorithm for discrete
logarithm in finite fields of small characteristic, http://eprint.iacr.org/2013/400[BCS] D. J. Bernstein, Tung Chou, Peter Schwabe, McBits: fast constant-time code-based cryptography, CHES 2013, to appear.
[BFLW] M. Bordewich, M. H. Freedman, L. Lovász and D. Welsh, Approximate counting andquantum computation, Combinatorics, Probability and Computing, 14(2005), 737-754.
[BMSS] A. Bostan, F. Morain, B. Salvy and É Schost: Fast algorithms for computing isogenies
between elliptici curves, Math. Comp. 77 (2008), 1755-1778.
[CEP] E. R. Canfield, P. Erdős, C. Pomerance, On a problem of Oppenheim concerning Factorisatio Numerorum, J. Number Theory 17 (1983) 1-28.
[CS] R. Cramer and V. Shoup, Signature Schemes based on strong RSA assumptions, Extended
abstract in Proc. ACM CCS 1999.
[CP] R. Crandall and C. Pomerance, Prime Numbers – A Computational Perspective, Springer,
2004.

24

Preda Mihăilescu and Michael Th. Rassias[DH] Whitfield Diffie and Martin Hellman, New Directions in Cryptography, IEEE Transactions
on Information Theory; Nov. 1976.
[EL] N. D. Elkies, Elliptic and modular curves over finite fields and related computational issues,Computational Perspectives on Number Theory: Proc. Conf. in honor of A. O. L. Atkin (D.
A. Buell and J. T. Teitelbaum, eds.), AMS/International Press, 1998, 21-76.
[ENI] Cryptanalysis of ENIGMA in Wikipedia :http://en.wikipedia.org/wiki/Cryptanalysis of the Enigma[Fre] M. H. Freedman, Complexity classes as mathematical axioms, Annals of Math., 170(2009),
995-1002.
[FKW] M. H. Freedman, A. Kitaev and Z. Wang, Simulation of topological field theories by quantum computers, Commun. Math. Phys., 227(2002), 587-603.
[FKLW] M. H. Freedman, A. Kitaev, M. J. Larsen and Z. Wang, Topological quantum computation, Bull. Amer. Math. Soc., 40(2003), 31-38.
[FLW] M. H. Freedman, M. J. Larsen and Z. Wang, Density representations of braid groups anddistribution of values of Jones invariants, Commun. Math. Phys. 228(2002), 177-199.
[FLW2] M. H. Freedman, M. J. Larsen and Z. Wang, A modular functor which is universal for
quantum computation, Commun. Math. Phys., 227(2002), 605-622.
[HeSSL] F. Heß, A. Stein, S. Stein and M. Lochter, The Magic of Elliptic Curves and Public Key
Cryptography, Jahresbericht Deutsch Math.-Ver. 114 (2012), 59-88.
[HPS] J. Hoffstein, J. Pipher and J.H. Silverman: An Introduction to Mathematical Cryptography,
Springer (2008)[Jo] A. Joux: A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic, http://eprint.iacr.org/2013/095[Ka] D. Kahn: The Codebreakers: The Comprehensive History of Secret Communication from
Ancient Times to the Internet, Scribner (1997).
[Kb1] N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48(1987), 203-209.
[Kb2] N. Koblitz, Course in Number Theory and Cryptography, Springer-Verlag, New York,
1994.
[Len] H. W. Lenstra, Factoring integers with elliptic curves, Annals Math., 126(3)(1987), 649673.
[Ma] U. Maurer: Towards the equivalence of breaking the Diffie-Hellman protocol and computing
discrete logarithms. Advances in Cryptology - Crypto ’94, Springer-Verlag, (1994), 271-281.
[McE] R. J. McEliece (January and February 1978), A Public-Key Cryptosystem Based On Algebraic Coding Theory, DSN Progress Report. 42-44: 114. Bibcode:1978DSNPR..44..114M.
[MMS] Mihăilescu, P., Morain, F., and Schost, .: Computing the eigenvalue in the Schoof-ElkiesAtkin algorithm using Abelian lifts. In ISSAC ’07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation (New York, NY, USA, 2007), ACM Press,
pp. 285-292.
[MR] P. Mihăilescu and M. Th. Rassias, Public key cryptography, number theory and applications, Newsletter of the European Mathematical Society, 86(2012), 25-30.
[MV] P. Mihăilescu and V. Vuletescu, Elliptic Gauss sums and applications to point counting. J.
Symb. Comput. 45, 8(2010), 825-836.
[ML] V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology: Proc. of Crypto’85, Lecture Notes in Computer Science, 218(1986), Springer-Verlag, New York, pp. 417426.
[MSU] A. Myasnikov, V. Shpilrain and A. Ushakov, Group-based Cryptography, Advanced
Courses in Math. CRM Barcelona, Birkhäuser Verlag (2008)[Ra] M. Th. Rassias, On the representation of the number of integral points of an elliptic curve
modulo a prime number, http://arxiv.org/abs/1210.1439[RSA] R. Rivest, A. Shamir and L. Adleman, A method for obtaining signatures and public key
cryptography, Communications of the ACM, 21 (1978), 121-126.
[Sc1] R. Schoof, Elliptic Curves over Finite Fields and Computation of Square Roots mod p,
Math. Comp. 43(1985), 483-494.
[Sc2] R. Schoof, Counting Point on Elliptic Curves over Finite Fields, Journal de Th. des Nombres
Bordeaux,

1 Computational Number Theory and Cryptography †25[Sil] J. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106,
Springer-Verlag, New York, 1986.
[Was] L. C. Washington, Elliptic Curves-Number Theory and Cryptography, CRC Press, London,
New York, 2008.