Cryptography

Cryptography is the science and practice of securing communication and Information by encoding it in such a way that only authorized parties can access it. It involves techniques for converting plaintext (readable data) into ciphertext (encoded data) and vice versa. Cryptography plays a crucial role in various fields such as computer security, e-commerce, banking, and national security. Here are some key details about cryptography:

Types of Cryptography:

 

Symmetric Cryptography: In symmetric cryptography, the same key is used for both encryption and decryption. Examples include cease Cipher, Affine Cipher,DES (Data Encryption Standard), AES (Advanced Encryption Standard), and 3DES (Triple Data Encryption Standard).

Asymmetric Cryptography: Also known as public-key cryptography, asymmetric cryptography uses two keys, a public key for encryption and a private key for decryption. RSA (Rivest-Shamir-Adleman) and ECC (Elliptic Curve Cryptography) are common asymmetric encryption algorithms.

 

We will study the details about these algorithms later in the course.

Secret codes have been used since ancient times to send messages securely, for instance in the times of war or diplomatic tension.Nowadays sensitive information of a medical or financial nature is often stored in computers and it is important to keep it secret.

Many codes are based on number theory. A simple one is to replace each letter of the alphabet with its successor. Mathematically, we can do this by representing the letters as integers, say $A = 0, B= 1,..., Z = 25$, and then adding 1 to each. In order to encode $Z$ as $A$, we must add $\pmod{26}$, so that 25 + 1 = 0. Similar codes are obtained by adding some fixed integer $k$ (known as the key), rather than 1: Julius Caesar used the key $k = 3.$ To decode, we simply apply the reverse transformation, subtracting $k \pmod {26}$.

These codes are easy to break. We could either try all possible values of $k$ in turn until we get a comprehensible message, or we could compare the most frequent letter in the message with the known most frequent letters in the original language (E, and then T, in English), to find $k$.

A slightly more secure class of codes uses affine transformations of the form $x \to ax +b \pmod {26}$, for various integers $a$ and $b$. To decode successfully, we need to be able to recover the value of $x$ uniquely from $ax + b$; this is possible if and only if $a$ is a unit $\pmod {26}$ ( ie; inverse of $a$ must exit), so by counting the pairs $a,b$ we see that there are $\phi(26).26 = 12.26 = 312$ such codes. Breaking such a code by trying all the possibilities for $a$ and $b$ would be tedious by hand (though simple with a computer), but again frequency searches can make the task much easier.

We can do rather better with codes based on Fermat’s Little Theorem. The idea is as follows. We choose a large prime $p$, and an integer $e$ coprime to $p-1$. 

 

For encoding, we use the transformation $Z_p,\to Z_p$, given by $x \to x^e \pmod{p}$.If $0 < x < p$ then $z$ will be coprime to $p$, so $z^{p-1}\equiv 1 \pmod {p}$. To decode, we first find the multiplicative inverse $f$ of $e \pmod {p— 1}$, that is, we solve the congruence $ef \equiv 1 \pmod {p— 1}$,this is possible since $e$ is a unit $\pmod {p—1}$. Then $ef = (p—1)k+1$ for some integer $k$, so 

$$(x^e)^f = x^{(p-1)k +1} = x^{(p-1)k}.x = x \pmod{p}$$. 

 

Thus we can determine $x$ from $x^e$, simply by raising it to the $f$-th power, so the message can be decoded efficiently.

 

Note: here two keys are used $e$ for encryption and $f$ for decryption.

Example:

Suppose that $p = 29$ .We must choose $e$ coprime to $p-1 = 28$, and then find $f$ such that $ef = 1 \pmod {28}$. If we take $e=5$, for example, so that encoding is given by $x \to x^5 \pmod {29}$, then $f = 17$ and decoding is given by $x \to  x^{17} \pmod {29}$. 

 

Note that $(x^5)^{17} = x^{85} = (x^{28})^3.x = x \pmod{29}$ for all $x$ coprime to 29, so decoding is the inverse of encoding.

Representing individual letters as numbers tends to be insecure, since an eavesdropper could use known frequencies of letters. A better method is to group the letters into blocks of length $k$, and to represent each block as an integer $x$. (If the length of the message is not divisible by $k$, one can always add extra meaningless letters at the end.) We choose $p$ sufficiently large that the distinct blocks of length $k$ can be represented by different congruence classes $x \not \equiv 0 \pmod {p}$, and then the encoding and decoding are given as before by
$x \to x^e \pmod{p}$ and $x \to x^f \pmod{p}$.

Breaking this code seems to be very difficult. Suppose, for instance, that an eavesdropper has discovered the value of $p$ being used, and also knows one pair $x$ and $y \equiv x^e \pmod{p}$. To break the code, he needs to know the value of $f$ (or equivalently $e$), but if $p$ is sufficiently large (say a hundred or more decimal digits) then there is no known efficient algorithm for calculating $e$ from the congruence $y = x^e \pmod{p}$, where $x$, $y$ and $p$ are known. This is sometimes called the discrete logarithm problem, since we can regard this congruence as a modular version of the equation $e = log_x(y)$. The whole point of this code is that, while exponentials are easy to calculate in modular arithmetic, logarithms are apparently difficult.

The one weakness of this type of code is that the sender and receiver must first agree on the values of $p$ and $e$ (called the key of the code) before they can use it. How can they do this secretly, bearing in mind that they will probably need to change the key from time to time for security? They could, of course exchange this information in encoded form, but then they would have to agree about the details of the code used for discussing the key, so they are no nearer solving the problem.

One can avoid this difficulty by using a public-key cryptographic system.Each person using the system publishes numerical information which enables any other user to encode messages, without giving away sufficient information to allow anyone but himself to decode them. Specifically, each person chooses a pair of large primes $p$ and $q$, calculates $n = pq$, and publishes its value. If $p$ and $q$ are sufficiently large, then $n$ cannot be factorised in a reasonable amount of time, so the values of $p$ and $q$ are effectively secret. Now $\phi(n)= (p -1)(q -1)$ so he (alone) can easily calculate $\phi(n)$; keeping $\phi(n)$ secret, he then finds and publishes an integer e coprime to $\phi(n)$. Anyone wishing to communicate with him looks up his published values for $n$ and $e$(this pair is the public key), and encodes the message by the method of exponentiation described earlier; the only difference is that the calculations are now done in $Z_n$, rather than $Z_p$, so that the encoding transformation is $x \to  x^e \pmod{n}$.Since $e$ is coprime to $\phi(n)$, the receiver (alone) can easily find $d$ such that $ed =1 \pmod {\phi(n)}$; if $x$ is coprime to $n$ (and this is easily arranged), then $(x^e)^d \equiv  x \pmod{n}$ by Euler’s Theorem, so he can use exponentiation to decode the message.This is the idea behind the famous public key crypto system RSA (Rivest-Shamir-Adleman).

 

RSA(Rivest–Shamir–Adleman) Algorithm ( public key cryptography)

1. Key Generation:

   • Choose two large prime numbers, $�$ and $�$, randomly.
   • Compute their product, $�=�\times �$, which serves as the modulus for both the public and private keys.
   • Compute Euler's totient function $�(�)=(�-1)\times (�-1)$.
   • Choose a public exponent $�$ that is relatively prime to $�(�)$ (i.e., $�$ has no common factors with $�(�)$ other than 1).
   • Compute the private exponent $�$ such that $�\times �\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}�(�))$, using the extended Euclidean algorithm.

2. Public and Private Key Generation:

   • The public key is $(�,�)$.
   • The private key is $(�,�)$.

3. Encryption:

   • Sender wants to send a message $�$ to the receiver.
   • The sender obtains the receiver's public key $(�,�)$.
   • Represent the message $�$ as an integer such that $0\le �<�$.
   • Compute the ciphertext $�$ using the encryption function: $�\equiv {�}^{�}(\mathrm{m}\mathrm{o}\mathrm{d}�)$.
   • Send the ciphertext $�$ to the receiver.

4. Decryption:

   • The receiver receives the ciphertext $�$.
   • The receiver uses their private key $(�,�)$ to decrypt the ciphertext.
   • Compute the original message $�$ using the decryption function: $�\equiv {�}^{�}(\mathrm{m}\mathrm{o}\mathrm{d}�)$.

Let's walk through a simple toy example of RSA encryption and decryption.

1. Key Generation:

   • Choose two prime numbers: $�=61$ and $�=53$.
   • Compute $�=�\times �=61\times 53=3233$.
   • Compute $�(�)=(�-1)\times (�-1)=60\times 52=3120$.
   • Choose a public exponent: let's use $�=17$.
   • Compute the private exponent $�$ such that $�\times �\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}�(�))$. Using the extended Euclidean algorithm, we find that $�=2753$.

   So, our public key is $(�,�)=(17,3233)$ and our private key is $(�,�)=(2753,3233)$.

2. Encryption:

   • Suppose we want to encrypt the message $�=123$.
   • To encrypt $�$, we compute $�\equiv {�}^{�}(\mathrm{m}\mathrm{o}\mathrm{d}�)$: $�\equiv 123^{17}(\mathrm{m}\mathrm{o}\mathrm{d}3233)$ $�\equiv 855(\mathrm{m}\mathrm{o}\mathrm{d}3233)$

   So, our ciphertext $�$ is 855.

3. Decryption:

   • To decrypt $�$, we use our private key $�=2753$: $�\equiv {�}^{�}(\mathrm{m}\mathrm{o}\mathrm{d}�)$ $�\equiv 855^{2753}(\mathrm{m}\mathrm{o}\mathrm{d}3233)$ $�\equiv 123(\mathrm{m}\mathrm{o}\mathrm{d}3233)$

   So, our decrypted message $�$ is 123, which matches the original message.

In this toy example, we've demonstrated how RSA encryption and decryption work with a small prime number example. In practice, much larger prime numbers are used to ensure the security of the RSA algorithm.

Consider Another Example:

Suppose that $p = 89$ and $q = 97$ are chosen, so $n = 89.97$ = 8633 is published,while $\phi(n)= 88.96 = 8448$. The receiver chooses and publishes an integer $e$ coprime to $\phi(n)$, say $e=71$. He then finds (and keeps secret) the multiplicative inverse $d=119$ of $71 \pmod{8448}$; to check this, note that $71.119 = 8449 = 1 \pmod {8448}$. 

To send a message $M$, anyone can look up the pair $n = 8633,e = 71$, and use the encoding $M \to M^{71} \pmod{8633}$. If $M=5$ , then $C=5^{71} \pmod{8633}=791$

The receiver uses the decoding transformation $C^d \pmod{8633}= C^{119} \pmod {8633}=791^{119} \pmod{8633}=5$, which is not available to anyone who does not know that $d= 119$. 

 

An eavesdropper would need to factorise $n = 8633$ in order to find $\phi(n)$ and then $d$. Of course, factorising 8633 is not so difficult, but this is just a simple illustration of the method, and significantly larger primes $p$ and $q$ would pose a much harder problem.

This system also gives a way of ‘signing’ a message, to prove to a receiver that it comes from you and from nobody else. First decode your name, using your $n$ and $d$ (the latter being secret to you). Then encode the result, using the receiver’s $n$ and $e$ (which are public knowledge), and send it to him. He will decode this message with his own $n$ and $d$, and then encode the result with your $n$ and $e$ (which are also public knowledge). 

 

At the end of this, the receiver should have your name, since he has inverted the two transformations which you applied to it. Only you could have correctly applied the first transformation,so he knows that the message must have come from you.This is the idea behind signature algorithm.

Summary

Public key cryptography, also known as asymmetric cryptography, allows two parties to securely communicate over an insecure channel without needing to share a secret key beforehand. Here are the basic steps involved in public key cryptography:

1. Key Generation:

   • Each party generates a pair of keys: a public key and a private key.
   • The public key is shared openly with anyone, while the private key is kept secret.
   • The keys are typically generated using mathematical algorithms, such as RSA or ECC.

2. Encryption:

   • Sender wants to send a message to the receiver.
   • The sender obtains the receiver's public key from a trusted source (e.g., public key infrastructure, key exchange protocols, etc.).
   • The sender encrypts the message using the receiver's public key.
   • The encrypted message can only be decrypted using the receiver's corresponding private key, ensuring confidentiality.

3. Transmission:

   • The sender transmits the encrypted message over the insecure channel.
   • As the message is encrypted, even if it's intercepted by an adversary, it cannot be deciphered without the private key.

4. Decryption:

   • The receiver receives the encrypted message.
   • The receiver decrypts the message using their private key, which only they possess.
   • As the decryption process requires the private key, only the intended receiver can read the original message.

5. Authentication and Digital Signatures :

   • Public key cryptography can also be used for authentication and ensuring data integrity.
   • The sender can digitally sign a message using their private key, creating a digital signature.
   • The receiver can verify the authenticity of the message and its integrity by verifying the digital signature using the sender's public key.

These steps illustrate the basic principles of public key cryptography, providing secure communication over insecure channels and enabling various security features such as confidentiality, authenticity, and data integrity.