Namespaces
Variants
Actions

Difference between revisions of "Cryptography"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
c0271701.png
 +
$#A+1 = 146 n = 0
 +
$#C+1 = 146 : ~/encyclopedia/old_files/data/C027/C.0207170 Cryptography
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
During recent years the increase in the amount of studies concerning cryptography has been really explosive, and there are two main reasons for this. In the first place, the seminal idea of public key cryptography, apart from being of extraordinary interest on its own right, has created entirely new types of applications, some of which are rather contra-intuitive with respect to the common sense notions concerning communication between different parties. In the second place, the need for cryptography has increased tremendously due to various aspects of data security. This can be expressed briefly by saying that there are now really many  "positive"  applications of cryptography, whereas the earlier applications were mainly  "negative" , i.e., secret communication during wars, criminal activities, etc. Besides, it seems that the range of applications will become larger and larger with the expansion of electronic mail and similar systems.
 
During recent years the increase in the amount of studies concerning cryptography has been really explosive, and there are two main reasons for this. In the first place, the seminal idea of public key cryptography, apart from being of extraordinary interest on its own right, has created entirely new types of applications, some of which are rather contra-intuitive with respect to the common sense notions concerning communication between different parties. In the second place, the need for cryptography has increased tremendously due to various aspects of data security. This can be expressed briefly by saying that there are now really many  "positive"  applications of cryptography, whereas the earlier applications were mainly  "negative" , i.e., secret communication during wars, criminal activities, etc. Besides, it seems that the range of applications will become larger and larger with the expansion of electronic mail and similar systems.
  
 
Consider messages sent via an insecure channel (cf. [[Communication channel|Communication channel]]). (The channel might be a telephone line subject to wiretapping by an eavesdropper, or it might be some data storage device in an information system.) Such messages will be referred to as plaintext. To increase security, the sender encrypts the plaintext and sends the resulting cryptotext via the channel. The receiver then decrypts the cryptotext back to the plaintext. (Instead of plaintext and cryptotext, the terms cleartext and ciphertext are often used.)
 
Consider messages sent via an insecure channel (cf. [[Communication channel|Communication channel]]). (The channel might be a telephone line subject to wiretapping by an eavesdropper, or it might be some data storage device in an information system.) Such messages will be referred to as plaintext. To increase security, the sender encrypts the plaintext and sends the resulting cryptotext via the channel. The receiver then decrypts the cryptotext back to the plaintext. (Instead of plaintext and cryptotext, the terms cleartext and ciphertext are often used.)
  
The encryption and decryption are usually carried out in terms of a specific cryptosystem. Essentially, a cryptosystem specifies several (often infinitely many) keys. Each key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271701.png" /> determines an encryption function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271702.png" /> and a decryption function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271703.png" />. Cryptotext <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271704.png" /> is obtained from plaintext <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271705.png" /> using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271706.png" />:
+
The encryption and decryption are usually carried out in terms of a specific cryptosystem. Essentially, a cryptosystem specifies several (often infinitely many) keys. Each key $  K $
 +
determines an encryption function $  e _ {K} $
 +
and a decryption function $  d _ {K} $.  
 +
Cryptotext c $
 +
is obtained from plaintext $  w $
 +
using $  e _ {K} $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271707.png" /></td> </tr></table>
+
$$
 +
e _ {K} ( w)  = c.
 +
$$
  
 
Conversely,
 
Conversely,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271708.png" /></td> </tr></table>
+
$$
 +
d _ {K} ( c)  = w.
 +
$$
  
 
Thus,
 
Thus,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c0271709.png" /></td> </tr></table>
+
$$
 +
d _ {K} ( e _ {K} ( w))  = w.
 +
$$
  
More specifically, a cryptosystem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717010.png" /> consists of a plaintext space, a cryptotext space and a key space. All three items are at most countable. Typically, a plaintext space could be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717011.png" />, for some [[Alphabet|alphabet]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717012.png" />, or the set of all meaningful sentences in a natural language such as English. Similarly, the cryptotext space could be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717013.png" />, for some alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717014.png" />. Each key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717015.png" /> determines mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717017.png" /> in the sense discussed above. For instance, if the plaintext and cryptotext spaces are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717019.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717020.png" /> will be a translation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717021.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717022.png" /> (cf. [[Translation|Translation]]).
+
More specifically, a cryptosystem $  CS $
 +
consists of a plaintext space, a cryptotext space and a key space. All three items are at most countable. Typically, a plaintext space could be $  \Sigma  ^ {*} $,  
 +
for some [[Alphabet|alphabet]] $  \Sigma $,  
 +
or the set of all meaningful sentences in a natural language such as English. Similarly, the cryptotext space could be $  \Delta  ^ {*} $,  
 +
for some alphabet $  \Delta $.  
 +
Each key $  K $
 +
determines mappings $  e _ {K} $
 +
and $  d _ {K} $
 +
in the sense discussed above. For instance, if the plaintext and cryptotext spaces are $  \Sigma  ^ {*} $
 +
and $  \Delta  ^ {*} $,  
 +
then $  e _ {K} $
 +
will be a translation of $  \Sigma  ^ {*} $
 +
into $  \Delta  ^ {*} $(
 +
cf. [[Translation|Translation]]).
  
 
"Legal"  communication activities may be intercepted by an eavesdropper or cryptanalyst. In a good cryptosystem cryptanalysis will be very difficult. No satisfactory formalization of these notions has been found so far: formalizations do not capture the essential issues from the point of view of applications.
 
"Legal"  communication activities may be intercepted by an eavesdropper or cryptanalyst. In a good cryptosystem cryptanalysis will be very difficult. No satisfactory formalization of these notions has been found so far: formalizations do not capture the essential issues from the point of view of applications.
  
Perhaps the oldest and best known among all cryptosystems is called Caesar cipher or briefly CAESAR. Both the plaintext space and the cryptotext space consist in this case of all words over the English alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717023.png" /> (cf. [[Word|Word]]). The key space is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717024.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717025.png" /> is an element of the key space, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717026.png" /> is the morphism mapping each letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717027.png" /> letters ahead in the alphabet. (The ordering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717028.png" /> is the natural alphabetic one, and the end of the alphabet is continued cyclically to the beginning, cf. [[Lexicographic order|Lexicographic order]].) For instance,
+
Perhaps the oldest and best known among all cryptosystems is called Caesar cipher or briefly CAESAR. Both the plaintext space and the cryptotext space consist in this case of all words over the English alphabet $  \Sigma = \{ A \dots Z \} $(
 +
cf. [[Word|Word]]). The key space is $  \{ 0 \dots 25 \} $.  
 +
If $  K $
 +
is an element of the key space, then $  e _ {K} $
 +
is the morphism mapping each letter $  K $
 +
letters ahead in the alphabet. (The ordering of $  \Sigma $
 +
is the natural alphabetic one, and the end of the alphabet is continued cyclically to the beginning, cf. [[Lexicographic order|Lexicographic order]].) For instance,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717029.png" /></td> </tr></table>
+
$$
 +
e _ {25} ( IBM)  = HAL,\ \
 +
e _ {6} ( MUPID)  = SAVOJ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717030.png" /></td> </tr></table>
+
$$
 +
e _ {3} ( HELP)  = KHOS,\  e _ {0} ( CRYPTO)  = CRYPTO.
 +
$$
  
The decryption function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717031.png" /> corresponding to the key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717032.png" /> is defined by
+
The decryption function $  d _ {K} $
 +
corresponding to the key $  K $
 +
is defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717033.png" /></td> </tr></table>
+
$$
 +
d _ {K}  = \
 +
e _ {26 - K }  .
 +
$$
  
 
Thus,
 
Thus,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717034.png" /></td> </tr></table>
+
$$
 +
d _ {6} ( SAVOJ)  = \
 +
e _ {20} ( SAVOJ)  = \
 +
MUPID.
 +
$$
  
Clearly, in this case all functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717036.png" /> are bijections of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717037.png" /> onto <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717038.png" /> (cf. [[Bijection|Bijection]]).
+
Clearly, in this case all functions $  e _ {K} $
 +
and $  d _ {K} $
 +
are bijections of $  \Sigma  ^ {*} $
 +
onto $  \Sigma  ^ {*} $(
 +
cf. [[Bijection|Bijection]]).
  
The [[Cardinality|cardinality]] of the key space of CAESAR is very small. No cryptosystem with this property can be good in the sense described above: cryptanalysis can be carried out simply by trying all possible keys. This is particularly easy if the plaintext is in some natural language. Then, for reasonably long cryptotexts (say with length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717039.png" />), in general only one decryption key produces a meaningful plaintext. This redundancy of natural languages constitutes the foundation for the cryptanalysis of many cryptosystems; knowledge of the statistical distribution of individual letters, pairs of consecutive letters and triples of consecutive letters uncovers the correspondence between plaintext and cryptotext letters.
+
The [[Cardinality|cardinality]] of the key space of CAESAR is very small. No cryptosystem with this property can be good in the sense described above: cryptanalysis can be carried out simply by trying all possible keys. This is particularly easy if the plaintext is in some natural language. Then, for reasonably long cryptotexts (say with length $  \geq  10 $),  
 +
in general only one decryption key produces a meaningful plaintext. This redundancy of natural languages constitutes the foundation for the cryptanalysis of many cryptosystems; knowledge of the statistical distribution of individual letters, pairs of consecutive letters and triples of consecutive letters uncovers the correspondence between plaintext and cryptotext letters.
  
CAESAR is the oldest widely used cryptosystem. A great variety of other cryptosystems has been developed. A property shared by all of these classical cryptosystems is that, whenever one knows the encryption key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717040.png" />, one also knows the decryption key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717041.png" />. More explicitly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717042.png" /> is either immediately implied by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717043.png" /> or else can be computed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717044.png" /> without too much difficulty. Thus, if one is dealing with any of the classical cryptosystems, the encryption key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717045.png" /> must be kept secret: once it is publicized, the decryption key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717046.png" /> is given away.
+
CAESAR is the oldest widely used cryptosystem. A great variety of other cryptosystems has been developed. A property shared by all of these classical cryptosystems is that, whenever one knows the encryption key $  e _ {K} $,  
 +
one also knows the decryption key $  d _ {K} $.  
 +
More explicitly, $  d _ {K} $
 +
is either immediately implied by $  e _ {K} $
 +
or else can be computed from $  e _ {K} $
 +
without too much difficulty. Thus, if one is dealing with any of the classical cryptosystems, the encryption key $  e _ {K} $
 +
must be kept secret: once it is publicized, the decryption key $  d _ {K} $
 +
is given away.
  
The seminal idea of public key cryptosystems (as opposed to what has been called above  "classical"  systems) is due to W. Diffie and M. Hellman, [[#References|[a3]]]: the knowledge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717047.png" /> does not necessarily give away <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717048.png" />. More specifically, the computation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717049.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717050.png" /> may be intractable, at least for almost-all keys <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717051.png" />.
+
The seminal idea of public key cryptosystems (as opposed to what has been called above  "classical"  systems) is due to W. Diffie and M. Hellman, [[#References|[a3]]]: the knowledge of $  e _ {K} $
 +
does not necessarily give away $  d _ {K} $.  
 +
More specifically, the computation of $  d _ {K} $
 +
from $  e _ {K} $
 +
may be intractable, at least for almost-all keys $  K $.
  
 
The idea of public key cryptosystems is very simple — why was it presented so late in the history of cryptography? One apparent reason is that some theory of computational complexity had to be ready before the realization of the idea of public key cryptography (cf. [[Complexity theory|Complexity theory]]).
 
The idea of public key cryptosystems is very simple — why was it presented so late in the history of cryptography? One apparent reason is that some theory of computational complexity had to be ready before the realization of the idea of public key cryptography (cf. [[Complexity theory|Complexity theory]]).
Line 45: Line 117:
 
The system RSA due to R. Rivest, A. Shamir and L. Adleman [[#References|[a4]]], is by now the most tested one among the public key systems. At the time of writing (1988), nothing serious has come up against RSA.
 
The system RSA due to R. Rivest, A. Shamir and L. Adleman [[#References|[a4]]], is by now the most tested one among the public key systems. At the time of writing (1988), nothing serious has come up against RSA.
  
RSA is based on the fact that it is almost impossible to recover two large prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717052.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717053.png" /> from their product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717054.png" /> — at least according to the presently known factorization algorithms. On the other hand, large random prime numbers can be generated fast. The public key encryption is based on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717055.png" />, whereas decryption requires that one knows <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717057.png" />. Details are presented below.
+
RSA is based on the fact that it is almost impossible to recover two large prime numbers $  p $
 +
and $  q $
 +
from their product $  n = pq $—  
 +
at least according to the presently known factorization algorithms. On the other hand, large random prime numbers can be generated fast. The public key encryption is based on $  n $,  
 +
whereas decryption requires that one knows $  p $
 +
and $  q $.  
 +
Details are presented below.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717059.png" /> be two large random primes (typically, having at least 100 digits in their decimal representation). Denote
+
Let $  p $
 +
and $  q $
 +
be two large random primes (typically, having at least 100 digits in their decimal representation). Denote
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717060.png" /></td> </tr></table>
+
$$
 +
= pq \ \
 +
\textrm{ and } \ \
 +
\phi ( n)  = \
 +
( p - 1) ( q - 1).
 +
$$
  
(Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717061.png" /> is the [[Euler function|Euler function]].) Choose a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717062.png" /> relatively prime to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717063.png" /> and a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717064.png" /> satisfying the congruence
+
(Here $  \phi $
 +
is the [[Euler function|Euler function]].) Choose a number $  e > 1 $
 +
relatively prime to $  \phi ( n) $
 +
and a number $  d $
 +
satisfying the congruence
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717065.png" /></td> </tr></table>
+
$$
 +
ed  \equiv  1  (  \mathop{\rm mod}  \phi ( n)).
 +
$$
  
(Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717067.png" /> are relatively prime, the congruence has a solution. It can be found rapidly by the [[Euclidean algorithm|Euclidean algorithm]].)
+
(Since $  e $
 +
and $  \phi ( n) $
 +
are relatively prime, the congruence has a solution. It can be found rapidly by the [[Euclidean algorithm|Euclidean algorithm]].)
  
The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717068.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717069.png" />, referred to as the modulus and the encryption exponent, respectively, constitute the public encryption key. The cryptotext <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717070.png" /> will be the least positive remainder of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717071.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717072.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717073.png" /> is the plaintext word over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717074.png" />. One assumes that the length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717075.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717076.png" /> satisfies the inequalities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717077.png" />. This is to make sure that the modular calculations do not cause any ambiguities and that, on the other hand, the plaintext blocks are not too short.
+
The numbers $  n $
 +
and $  e $,  
 +
referred to as the modulus and the encryption exponent, respectively, constitute the public encryption key. The cryptotext c $
 +
will be the least positive remainder of $  w  ^ {e} $
 +
$  (  \mathop{\rm mod}  n) $,  
 +
where $  w $
 +
is the plaintext word over the alphabet $  \{ 0 \dots 9 \} $.  
 +
One assumes that the length $  i $
 +
of $  w $
 +
satisfies the inequalities $  10 ^ {i - 1 } < n < 10  ^ {i} $.  
 +
This is to make sure that the modular calculations do not cause any ambiguities and that, on the other hand, the plaintext blocks are not too short.
  
It can be shown by straightforward elementary number theory that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717078.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717079.png" />. Thus, the trapdoor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717080.png" /> enables one to decrypt.
+
It can be shown by straightforward elementary number theory that c ^ {d} \equiv w $
 +
$  (  \mathop{\rm mod}  n) $.  
 +
Thus, the trapdoor $  d $
 +
enables one to decrypt.
  
For example, choose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717081.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717082.png" />, yielding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717083.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717084.png" />. Choose further <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717085.png" />, yielding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717086.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717087.png" />, the plaintext blocks should consist of four decimal digits. For instance, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717088.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717089.png" />. For decryption, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717090.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717091.png" />.
+
For example, choose $  p = 47 $
 +
and $  q = 59 $,  
 +
yielding $  n = 2773 $
 +
and $  \phi ( n) = 2668 $.  
 +
Choose further $  e = 17 $,  
 +
yielding $  d = 157 $.  
 +
Since $  10  ^ {3} < n < 10  ^ {4} $,  
 +
the plaintext blocks should consist of four decimal digits. For instance, $  1920  ^ {17} \equiv 2109 $
 +
$  (  \mathop{\rm mod}  2773 ) $.  
 +
For decryption, $  2109  ^ {157} \equiv 1920 $
 +
$  (  \mathop{\rm mod}  2773) $.
  
It is rather easy to factorize 2773 and, hence, to find the decryption exponent <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717092.png" />. However, one might still want to consider the case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717093.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717094.png" /> are so large that they cannot be recovered from their product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717095.png" />. How could cryptanalysis be carried out in this case?
+
It is rather easy to factorize 2773 and, hence, to find the decryption exponent $  d = 157 $.  
 +
However, one might still want to consider the case where $  p $
 +
and $  q $
 +
are so large that they cannot be recovered from their product $  n $.  
 +
How could cryptanalysis be carried out in this case?
  
For instance, assume that one is able to compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717096.png" /> without actually factorizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717097.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717098.png" /> is immediately obtainable from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c02717099.png" /> and the public information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170100.png" />. On the other hand, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170101.png" /> is the square root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170102.png" /> and, thus, also immediately obtainable. Now <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170103.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170104.png" /> can be immediately computed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170105.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170106.png" />. This means that an algorithm for computing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170107.png" /> yields an algorithm of essentially the same complexity for factorizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170108.png" />.
+
For instance, assume that one is able to compute $  \phi ( n) $
 +
without actually factorizing $  n $.  
 +
Then $  p + q $
 +
is immediately obtainable from $  \phi ( n) = n - ( p + q) + 1 $
 +
and the public information $  n $.  
 +
On the other hand, $  p - q $
 +
is the square root of $  ( p + q)  ^ {2} - 4n $
 +
and, thus, also immediately obtainable. Now $  p $
 +
and $  q $
 +
can be immediately computed from $  p + q $
 +
and $  p - q $.  
 +
This means that an algorithm for computing $  \phi ( n) $
 +
yields an algorithm of essentially the same complexity for factorizing $  n $.
  
 
Public key cryptosystems are especially suitable for authentication and electronic signatures.
 
Public key cryptosystems are especially suitable for authentication and electronic signatures.
  
Consider two parties <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170109.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170110.png" /> with conflicting interests, e.g. a bank and a customer or two superpowers. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170111.png" /> sends a message to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170112.png" />, it should be signed and the signature should give the parties the following two kinds of protection.
+
Consider two parties $  A $
 +
and $  B $
 +
with conflicting interests, e.g. a bank and a customer or two superpowers. When $  A $
 +
sends a message to $  B $,  
 +
it should be signed and the signature should give the parties the following two kinds of protection.
  
i) Both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170113.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170114.png" /> should be protected against messages addressed to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170115.png" />, fed in the information system by a third party <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170116.png" /> who pretends to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170117.png" />.
+
i) Both $  A $
 +
and $  B $
 +
should be protected against messages addressed to $  B $,  
 +
fed in the information system by a third party $  C $
 +
who pretends to be $  A $.
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170118.png" /> should be protected against messages forged by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170119.png" /> who claims to have received them from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170120.png" />, properly signed.
+
ii) $  A $
 +
should be protected against messages forged by $  B $
 +
who claims to have received them from $  A $,  
 +
properly signed.
  
If a classical cryptosystem is used, then the requirement i) can be satisfied in a reasonable fashion: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170121.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170122.png" /> agree upon a secret encryption key known only to them. On the other hand, the requirement ii) is apparently more difficult to satisfy because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170123.png" /> should know something about the way <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170124.png" /> generates the signature, and yet it should be impossible for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170125.png" /> to generate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170126.png" />'s signature. Observe also that if one is dealing with a big network of communicating parties (say, a network of mail users) then it is impractical to use a distinct secret method of signing for every pair of users.
+
If a classical cryptosystem is used, then the requirement i) can be satisfied in a reasonable fashion: $  A $
 +
and $  B $
 +
agree upon a secret encryption key known only to them. On the other hand, the requirement ii) is apparently more difficult to satisfy because $  B $
 +
should know something about the way $  A $
 +
generates the signature, and yet it should be impossible for $  B $
 +
to generate $  A $'
 +
s signature. Observe also that if one is dealing with a big network of communicating parties (say, a network of mail users) then it is impractical to use a distinct secret method of signing for every pair of users.
  
If a public key cryptosystem is used, both i) and ii) can be satisfied, at least in principle. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170127.png" /> sends the message <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170128.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170129.png" /> in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170130.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170131.png" /> can first recover <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170132.png" /> by the secret decryption key <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170133.png" />. From <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170134.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170135.png" /> can recover <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170136.png" /> by the publicly known <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170137.png" />. (Recall that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170138.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170139.png" /> are inverses.) Now both i) and ii) are satisfied because only <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170140.png" /> knows <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170141.png" />. Hence, neither <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170142.png" /> nor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170143.png" /> forge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170144.png" />'s signature. Also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170145.png" /> cannot later deny sending the message to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027170/c027170146.png" />.
+
If a public key cryptosystem is used, both i) and ii) can be satisfied, at least in principle. $  A $
 +
sends the message $  w $
 +
to $  B $
 +
in the form $  e _ {B} ( d _ {A} ( w)) $.  
 +
$  B $
 +
can first recover $  d _ {A} ( w) $
 +
by the secret decryption key $  d _ {B} $.  
 +
From $  d _ {A} ( w) $,  
 +
$  B $
 +
can recover $  w $
 +
by the publicly known $  e _ {A} $.  
 +
(Recall that $  e _ {A} $
 +
and $  d _ {A} $
 +
are inverses.) Now both i) and ii) are satisfied because only $  A $
 +
knows $  d _ {A} $.  
 +
Hence, neither $  C $
 +
nor $  B $
 +
forge $  A $'
 +
s signature. Also $  A $
 +
cannot later deny sending the message to $  B $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Beker,  F. Piper,  "Cipher systems" , Northwood Books  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.E. Denning,  "Cryptography and data security" , Addison-Wesley  (1982)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W. Diffie,  M. Hellman,  "New directions in cryptography"  ''IEEE Trans. Information Theory'' , '''IT-22'''  (1976)  pp. 644–654</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Rivest,  A. Shamir,  L. Adleman,  "A method for obtaining digital signatures and public-key cryptosystems"  ''Comm. ACM'' , '''21'''  (1978)  pp. 120–126</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Salomaa,  "Computation and automata" , Cambridge Univ. Press  (1985)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Beker,  F. Piper,  "Cipher systems" , Northwood Books  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.E. Denning,  "Cryptography and data security" , Addison-Wesley  (1982)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W. Diffie,  M. Hellman,  "New directions in cryptography"  ''IEEE Trans. Information Theory'' , '''IT-22'''  (1976)  pp. 644–654</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Rivest,  A. Shamir,  L. Adleman,  "A method for obtaining digital signatures and public-key cryptosystems"  ''Comm. ACM'' , '''21'''  (1978)  pp. 120–126</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Salomaa,  "Computation and automata" , Cambridge Univ. Press  (1985)</TD></TR></table>

Latest revision as of 17:31, 5 June 2020


During recent years the increase in the amount of studies concerning cryptography has been really explosive, and there are two main reasons for this. In the first place, the seminal idea of public key cryptography, apart from being of extraordinary interest on its own right, has created entirely new types of applications, some of which are rather contra-intuitive with respect to the common sense notions concerning communication between different parties. In the second place, the need for cryptography has increased tremendously due to various aspects of data security. This can be expressed briefly by saying that there are now really many "positive" applications of cryptography, whereas the earlier applications were mainly "negative" , i.e., secret communication during wars, criminal activities, etc. Besides, it seems that the range of applications will become larger and larger with the expansion of electronic mail and similar systems.

Consider messages sent via an insecure channel (cf. Communication channel). (The channel might be a telephone line subject to wiretapping by an eavesdropper, or it might be some data storage device in an information system.) Such messages will be referred to as plaintext. To increase security, the sender encrypts the plaintext and sends the resulting cryptotext via the channel. The receiver then decrypts the cryptotext back to the plaintext. (Instead of plaintext and cryptotext, the terms cleartext and ciphertext are often used.)

The encryption and decryption are usually carried out in terms of a specific cryptosystem. Essentially, a cryptosystem specifies several (often infinitely many) keys. Each key $ K $ determines an encryption function $ e _ {K} $ and a decryption function $ d _ {K} $. Cryptotext $ c $ is obtained from plaintext $ w $ using $ e _ {K} $:

$$ e _ {K} ( w) = c. $$

Conversely,

$$ d _ {K} ( c) = w. $$

Thus,

$$ d _ {K} ( e _ {K} ( w)) = w. $$

More specifically, a cryptosystem $ CS $ consists of a plaintext space, a cryptotext space and a key space. All three items are at most countable. Typically, a plaintext space could be $ \Sigma ^ {*} $, for some alphabet $ \Sigma $, or the set of all meaningful sentences in a natural language such as English. Similarly, the cryptotext space could be $ \Delta ^ {*} $, for some alphabet $ \Delta $. Each key $ K $ determines mappings $ e _ {K} $ and $ d _ {K} $ in the sense discussed above. For instance, if the plaintext and cryptotext spaces are $ \Sigma ^ {*} $ and $ \Delta ^ {*} $, then $ e _ {K} $ will be a translation of $ \Sigma ^ {*} $ into $ \Delta ^ {*} $( cf. Translation).

"Legal" communication activities may be intercepted by an eavesdropper or cryptanalyst. In a good cryptosystem cryptanalysis will be very difficult. No satisfactory formalization of these notions has been found so far: formalizations do not capture the essential issues from the point of view of applications.

Perhaps the oldest and best known among all cryptosystems is called Caesar cipher or briefly CAESAR. Both the plaintext space and the cryptotext space consist in this case of all words over the English alphabet $ \Sigma = \{ A \dots Z \} $( cf. Word). The key space is $ \{ 0 \dots 25 \} $. If $ K $ is an element of the key space, then $ e _ {K} $ is the morphism mapping each letter $ K $ letters ahead in the alphabet. (The ordering of $ \Sigma $ is the natural alphabetic one, and the end of the alphabet is continued cyclically to the beginning, cf. Lexicographic order.) For instance,

$$ e _ {25} ( IBM) = HAL,\ \ e _ {6} ( MUPID) = SAVOJ, $$

$$ e _ {3} ( HELP) = KHOS,\ e _ {0} ( CRYPTO) = CRYPTO. $$

The decryption function $ d _ {K} $ corresponding to the key $ K $ is defined by

$$ d _ {K} = \ e _ {26 - K } . $$

Thus,

$$ d _ {6} ( SAVOJ) = \ e _ {20} ( SAVOJ) = \ MUPID. $$

Clearly, in this case all functions $ e _ {K} $ and $ d _ {K} $ are bijections of $ \Sigma ^ {*} $ onto $ \Sigma ^ {*} $( cf. Bijection).

The cardinality of the key space of CAESAR is very small. No cryptosystem with this property can be good in the sense described above: cryptanalysis can be carried out simply by trying all possible keys. This is particularly easy if the plaintext is in some natural language. Then, for reasonably long cryptotexts (say with length $ \geq 10 $), in general only one decryption key produces a meaningful plaintext. This redundancy of natural languages constitutes the foundation for the cryptanalysis of many cryptosystems; knowledge of the statistical distribution of individual letters, pairs of consecutive letters and triples of consecutive letters uncovers the correspondence between plaintext and cryptotext letters.

CAESAR is the oldest widely used cryptosystem. A great variety of other cryptosystems has been developed. A property shared by all of these classical cryptosystems is that, whenever one knows the encryption key $ e _ {K} $, one also knows the decryption key $ d _ {K} $. More explicitly, $ d _ {K} $ is either immediately implied by $ e _ {K} $ or else can be computed from $ e _ {K} $ without too much difficulty. Thus, if one is dealing with any of the classical cryptosystems, the encryption key $ e _ {K} $ must be kept secret: once it is publicized, the decryption key $ d _ {K} $ is given away.

The seminal idea of public key cryptosystems (as opposed to what has been called above "classical" systems) is due to W. Diffie and M. Hellman, [a3]: the knowledge of $ e _ {K} $ does not necessarily give away $ d _ {K} $. More specifically, the computation of $ d _ {K} $ from $ e _ {K} $ may be intractable, at least for almost-all keys $ K $.

The idea of public key cryptosystems is very simple — why was it presented so late in the history of cryptography? One apparent reason is that some theory of computational complexity had to be ready before the realization of the idea of public key cryptography (cf. Complexity theory).

The system RSA due to R. Rivest, A. Shamir and L. Adleman [a4], is by now the most tested one among the public key systems. At the time of writing (1988), nothing serious has come up against RSA.

RSA is based on the fact that it is almost impossible to recover two large prime numbers $ p $ and $ q $ from their product $ n = pq $— at least according to the presently known factorization algorithms. On the other hand, large random prime numbers can be generated fast. The public key encryption is based on $ n $, whereas decryption requires that one knows $ p $ and $ q $. Details are presented below.

Let $ p $ and $ q $ be two large random primes (typically, having at least 100 digits in their decimal representation). Denote

$$ n = pq \ \ \textrm{ and } \ \ \phi ( n) = \ ( p - 1) ( q - 1). $$

(Here $ \phi $ is the Euler function.) Choose a number $ e > 1 $ relatively prime to $ \phi ( n) $ and a number $ d $ satisfying the congruence

$$ ed \equiv 1 ( \mathop{\rm mod} \phi ( n)). $$

(Since $ e $ and $ \phi ( n) $ are relatively prime, the congruence has a solution. It can be found rapidly by the Euclidean algorithm.)

The numbers $ n $ and $ e $, referred to as the modulus and the encryption exponent, respectively, constitute the public encryption key. The cryptotext $ c $ will be the least positive remainder of $ w ^ {e} $ $ ( \mathop{\rm mod} n) $, where $ w $ is the plaintext word over the alphabet $ \{ 0 \dots 9 \} $. One assumes that the length $ i $ of $ w $ satisfies the inequalities $ 10 ^ {i - 1 } < n < 10 ^ {i} $. This is to make sure that the modular calculations do not cause any ambiguities and that, on the other hand, the plaintext blocks are not too short.

It can be shown by straightforward elementary number theory that $ c ^ {d} \equiv w $ $ ( \mathop{\rm mod} n) $. Thus, the trapdoor $ d $ enables one to decrypt.

For example, choose $ p = 47 $ and $ q = 59 $, yielding $ n = 2773 $ and $ \phi ( n) = 2668 $. Choose further $ e = 17 $, yielding $ d = 157 $. Since $ 10 ^ {3} < n < 10 ^ {4} $, the plaintext blocks should consist of four decimal digits. For instance, $ 1920 ^ {17} \equiv 2109 $ $ ( \mathop{\rm mod} 2773 ) $. For decryption, $ 2109 ^ {157} \equiv 1920 $ $ ( \mathop{\rm mod} 2773) $.

It is rather easy to factorize 2773 and, hence, to find the decryption exponent $ d = 157 $. However, one might still want to consider the case where $ p $ and $ q $ are so large that they cannot be recovered from their product $ n $. How could cryptanalysis be carried out in this case?

For instance, assume that one is able to compute $ \phi ( n) $ without actually factorizing $ n $. Then $ p + q $ is immediately obtainable from $ \phi ( n) = n - ( p + q) + 1 $ and the public information $ n $. On the other hand, $ p - q $ is the square root of $ ( p + q) ^ {2} - 4n $ and, thus, also immediately obtainable. Now $ p $ and $ q $ can be immediately computed from $ p + q $ and $ p - q $. This means that an algorithm for computing $ \phi ( n) $ yields an algorithm of essentially the same complexity for factorizing $ n $.

Public key cryptosystems are especially suitable for authentication and electronic signatures.

Consider two parties $ A $ and $ B $ with conflicting interests, e.g. a bank and a customer or two superpowers. When $ A $ sends a message to $ B $, it should be signed and the signature should give the parties the following two kinds of protection.

i) Both $ A $ and $ B $ should be protected against messages addressed to $ B $, fed in the information system by a third party $ C $ who pretends to be $ A $.

ii) $ A $ should be protected against messages forged by $ B $ who claims to have received them from $ A $, properly signed.

If a classical cryptosystem is used, then the requirement i) can be satisfied in a reasonable fashion: $ A $ and $ B $ agree upon a secret encryption key known only to them. On the other hand, the requirement ii) is apparently more difficult to satisfy because $ B $ should know something about the way $ A $ generates the signature, and yet it should be impossible for $ B $ to generate $ A $' s signature. Observe also that if one is dealing with a big network of communicating parties (say, a network of mail users) then it is impractical to use a distinct secret method of signing for every pair of users.

If a public key cryptosystem is used, both i) and ii) can be satisfied, at least in principle. $ A $ sends the message $ w $ to $ B $ in the form $ e _ {B} ( d _ {A} ( w)) $. $ B $ can first recover $ d _ {A} ( w) $ by the secret decryption key $ d _ {B} $. From $ d _ {A} ( w) $, $ B $ can recover $ w $ by the publicly known $ e _ {A} $. (Recall that $ e _ {A} $ and $ d _ {A} $ are inverses.) Now both i) and ii) are satisfied because only $ A $ knows $ d _ {A} $. Hence, neither $ C $ nor $ B $ forge $ A $' s signature. Also $ A $ cannot later deny sending the message to $ B $.

References

[a1] H. Beker, F. Piper, "Cipher systems" , Northwood Books (1982)
[a2] D.E. Denning, "Cryptography and data security" , Addison-Wesley (1982)
[a3] W. Diffie, M. Hellman, "New directions in cryptography" IEEE Trans. Information Theory , IT-22 (1976) pp. 644–654
[a4] R. Rivest, A. Shamir, L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems" Comm. ACM , 21 (1978) pp. 120–126
[a5] A. Salomaa, "Computation and automata" , Cambridge Univ. Press (1985)
How to Cite This Entry:
Cryptography. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cryptography&oldid=46558
This article was adapted from an original article by G. RozenbergA. Salomaa (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article