Unit - 4

Affine ciphers

4.1 Affine ciphers, Hill ciphers

4.1.1 Hill Ciphers

Hill cyphers (developed in 1929) are a type of block cypher in which the ciphertext character that replaces a certain plaintext character in the encryption is determined by the plaintext characters surrounding it. Matrix arithmetic is used to encrypt the information.

A square matrix of integers is used as the encryption key for a Hill cypher. These integers are drawn from the range 0 to 1, inclusive, n 1, where n is the size of the plaintext message character set. (If you use the standard English alphabet, n = 26.) It's worth noting that not all such square matrices are valid Hill cypher keys. Later, we'll go over what's required to create a valid key.

For now, suppose the key is the matrix and we want to encrypt the message “time to study” using a Hill cipher with this key. Using the conversion table:

0 1 2 3 4 5 6 7 8 9 10 11 12

A B C D E F G H I J K L M             

13 14 15 16 17 18 19 20 21 22 23 24 25

N O P Q R S T U V W X Y Z

Our plaintext message is represented as. 19:8:12:4:19:14:18:19:20:3:24:19:8:12:4 We now divide this sequence of numbers into three rows of length three (the size of ) to get

19 8 12

4 19 14

18 19 20

3 24  ?

In order for the encryption to continue, we must address the “?” in the last row. It's common practise to replace it with an integer that represents a plaintext letter that can be easily identified as unwanted when the message is received. We'll utilise the number 23, which stands for the letter "x." From the four rows that result, we create a matrix:

We now compute = using standard matrix multiplication, except that anytime an element x does not meet 0 x 25, we replace x with the integer y 0..., 25 so that y x (mod 26). As an example, in the current situation, this produces in

To get the ciphertext XQCHJAVRGPBT, concatenate the rows of to get the sequence 23 16 2 7 9 0 21 17 6 15 1 19 and replace each number with the letter it represents.

Try encrypting the plaintext "finals are coming" with the encryption key above using a Hill cypher, and see if you can produce the ciphertext JRDZDOPZMWOOVXG.

Using a Hill cypher and the same encryption key as before, the following ciphertext was generated:

COAOVZOZWJBH.

To produce the sequence 2 14 0 14 21 25 14 25 22 9 1 7, replace each ciphertext letter with the integer that represents it.

We now need to acquire from and. We could solve: if the connection (mod 26) were an equation instead of a congruence and an invertible matrix.

Since we have a congruence and not an equation, we have to take more care than this! There are two issues: do we have an inverse for κ, and, if so, what do we do if, (as is likely), κ −1 has non-integer entries? In this case, (as you can verify), we do have an inverse for κ:

This inverse, on the other hand, does not have integer elements. To continue with our decryption, we must substitute 1 27 with an integer that behaves similarly, i.e., when multiplied by 27, provides an answer that is equivalent to 1 modulo 26. (For further information, see the section on affine cyphers.) Fortunately, since 27 1 (mod 26), we can substitute 1 27 for 1 to get:

The plaintext “summerplansx” is recovered from here, and we determine that the message was “summer plans.” We can now determine what properties a square matrix of integers must have in order to be a valid key for a Hill cypher. We need to be invertible modulo 26 for the decryption process to work, which means that the determinant of must satisfy gcd(det, 26) = 1. (To understand the relationship between determinants and inverses, look up the classical adjoint of a matrix in your favourite linear algebra source.) Here's some additional practise for you. The ciphertext below was created by

a Hill cipher with key

EMRISXCAEGOHJEVI. Check to see if the plaintext can be recovered. (Keep in mind that your matrices and must have two columns if you're using a 2 2 key!) While Hill cyphers provide a major boost in security over Vigenere cyphers, they are vulnerable to known plaintext attacks if a few right characters of plaintext are previously matched to a ciphertext message. As a result, Hill cyphers aren't seen to be safe enough for sensitive applications.

4.1.2 Affine ciphers

The affine cypher is a monoalphabetic substitution cypher in which each letter of the alphabet is mapped to its numeric counterpart, encrypted with a simple mathematical function, and then transformed back to a letter. Because of the formula, each letter encrypts to one other letter and back, the cypher is effectively a substitution cypher with a rule determining which letter goes to which. As a result, it suffers from the same flaws as all other substitution cyphers. The function (axe + b) mod 26 is used to encode each letter, with b indicating the magnitude of the shift.

The letters of an alphabet of size m are first mapped to integers in the range 0... m 1 in the affine cypher. The integer that each plaintext letter refers to is then transformed into another integer that corresponds to a ciphertext letter using modular arithmetic. For a single letter, the encryption function is

The size of the alphabet is modulus m, and the cipher's keys are a and b. a must be chosen in such a way that a and m are coprime. The function of decryption is

Where a−1 is the modular multiplicative inverse of a modulo m. I.e., it satisfies the equation

If a and m are coprime, the multiplicative inverse of a exists. Decryption may not be possible without the restriction on a. The decryption function is the inverse of the encryption function, as shown below.

Numericals:

1) Assume the message is encrypted using the y = (11x + 4) MOD 26 function (Encipher)

To encrypt the plaintext MONEY, we must first convert each letter into a number value between 0 and 25 using the list below.

A – 0

B – 1

C – 2

D – 3

.

.

.

Z – 25

As a result, the plaintext MONEY has numerical values of 12, 14, 13, 4, and 24.

We have by applying the supplied function to each numerical value

M: y = (11*12 + 4) MOD 26 = 6

O: y = (11*14 + 4) MOD 26 = 2
N: y = (11*13 + 4) MOD 26 = 17
E : y = (11*4 + 4) MOD 26 = 22
Y : y = (11*24 + 4) MOD 26 = 8

The corresponding letters are GCRWI, which is the ciphertext.

(Decipher)

To decipher, we transform the function y as:

x = inverse (a) (y – b) MOD m

Then we have, x = inverse(11) (y – 4) MOD 26

Inverse(11) MOD 26 = 19, and the decryption function will be x = 19 (y – 4) MOD 26

We now decipher the ciphertext GCRWI by applying the decryption function. We have:

G: x = 19*(6-4) MOD 26 = 12
C: x = 19*(2-4) MOD 26 = 14
R: x = 19*(17-4) MOD 26 = 13
W: x = 19*(22-4) MOD 26 = 4
I: x = 19*(8-4) MOD 26 = 24

MONEY is the plaintext letter that corresponds.

2) Encipher ITS COOL with

Solution:

Filling in the following table gives

	8	19	18	2	14	14	11
	48	103	98	18	78	78	63
	22	25	20	18	0	0	11
Cipher	W	Z	U	S	A	A	L

If y = E(x) = (ax+b) MOD 26, then we can “solve for x in terms of y” and so determine E−1 (y). That is, if y ≡ (ax + b) (mod 26), then y − b ≡ ax (mod 26), or equivalently ax ≡ (y − b) (mod 26). Using our earlier results, we see that if we multiply both sides by a −1 (mod 26), then x ≡ a −1 (y − b) (mod 26) and so our \

Decipherment function is

3) Decipher HPCCXAQ if the encipherment function is

Solution:

We begin by finding the decipherment function. Since 5x ≡ 1 (mod 26) is solved with x ≡ 21 (mod 26) we see 5−1 (mod 26) = 21. Therefore,

And so filling in our table gives

	7	15	2	2	23	0	11
	-1	7	-6	-6	15	-8	8
	-2	147	-126	-126	315	-168	168
	5	17	4	4	3	14	12

4) Suppose that an affine cipher E(x) = (ax + b) MOD 26 enciphers H as X and Q as Y. Find the cipher (that is, determine a and b).

Solution:

We see that

That is,

Subtracting gives 16a − 7a ≡ 1 (mod 26) so that 9a ≡ 1 (mod 26). Therefore, a = 9−1 (mod 26) = 3. Finally, we substitute a = 3 into either of the earlier equations and solve for b,

In summary,

Key takeaways:

The Hill Cipher is a cryptographic algorithm that uses modulo arithmetic. This cryptography approach encrypts and decrypts using a square matrix as the key. When the Hill Cipher algorithm is used in the process of sending and receiving data, security is assumed to be guaranteed.

4.2 Public key cryptography, RSA encryption and decryption

• The RSA algorithm is a public key encryption technology that is widely regarded as the most secure. Rivest, Shamir, and Adleman devised the RSA algorithm in 1978, hence the name.

• In the standard alphabet, there are 12 numbers smaller than 26 that are coprime to 26, and each of them has 26 potential values for b, giving us a total of 12 x 26 = 312 keys for the Affine Cipher.

4.2.1 Algorithm

• The RSA algorithm is a common exponentiation in a finite field over integers, including prime numbers, with sufficiently large integers to make it difficult to solve.

• This algorithm uses two sets of keys: a private key and a public key. To work on the RSA algorithm, you must go through the stages below.

• Generate the RSA modulus in step one.

The first step is to choose two prime numbers, p and q, and then calculate their product N, as illustrated in the diagram.

N=p*q

Let N be the specified huge number in this case.

• Derived Number (Step 2)

Consider e as a derived number that must be larger than 1 but less than (p-1) and (q-1) The fundamental criterion will be that no common factor of (p-1) and (q-1) other than 1 exists.

• Step 3: Generate a public key

The RSA public key is formed by the stated pair of numbers n and e, and it is made public.

• Step 4: Obtaining a Private Key

The numbers p, q, and e are used to calculate Private Key d. The following is the mathematical relationship between the numbers:

1 mod (p-1) = ed (q-1)

The basic formula for the Extended Euclidean Algorithm, which takes p and q as input parameters, is shown above.

4.2.2 Encryption Formula

Consider the case of a sender who sends a plain text message to a recipient whose public key is (n,e). Use the following to encrypt the plain text message in the given case.

Syntax −

C = Pe mod n

Examples:

1) The RSA public-key encryption method is used to encrypt plaintext 9 in this example. The public and private keys in this example are generated using prime integers 7 and 11.

Solution:

Step 1: p and q are two huge prime numbers.

p = 7

q = 11

Step 2: Multiply these integers to get n = p x q, where n is the encryption and decryption modulus.

First, we calculate

n = p x q

n = 7 x 11

n = 77

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (7 - 1) x (11 - 1)

φ (n) = 6 x 10

φ (n) = 60

Let's use the number 7 as the relative prime e of 60.

Thus the public key is <e, n> = (7, 77)

Step 4: A plaintext message m is encrypted using public key <e, n>. To find ciphertext from the plain text following formula is used to get ciphertext C.

To obtain ciphertext C from plain text, apply the formula below.

C = me mod n

C = 97 mod 77

C = 37

Step 5: The private key is <d, n>. To determine the private key, we use the following formula d such that:

De mod {(p - 1) x (q - 1)} = 1

7d mod 60 = 1, which gives d = 43

The private key is <d, n> = (43, 77)

Step 6: The private key d, n> is used to decrypt a ciphertext message c. The following formula is used to calculate plain text m from ciphertext c. m = cd mod n

m = 3743 mod 77

m = 9

Plain text = 9 and ciphertext = 37 in this example.

4.2.3 Decryption Formula

The decryption process is simple and contains analytics for computation in a methodical manner. The result modulus will be calculated as if receiver C possesses the private key d.

4.2.4 Concepts of Public-Key Cryptography

It's time to find out our public key now that we know Carmichael's totient of our prime numbers. Public keys in RSA are made up of a prime integer e and modulus n. The value for (n) in our case is 349,716. The number e can be any number between 1 and the value for (n).

It's less crucial for e to be a random value because the public key is released publicly. In reality, e is usually set to 65,537 because choosing significantly larger integers at random reduces the efficiency of encryption. To make calculations easier, we'll keep the numbers small in today's example. Assume the following scenario:

e = 11

The ciphertext is the name given to our finished encrypted data (c). We get it from our plaintext message (m) by using the following formula using the public key:

c = me mod n

The public key is e mod n, as previously stated. We've previously figured out e, and we're familiar with n. Mod is the only thing we need to explain. It's a touch beyond the scope of this article, but a modulo operation refers to the residual left over when you divide one side by the other. Consider the following scenario:

10 mod 3 = 1

This is due to the fact that 3 is multiplied by 10 three times, leaving a leftover of 1.

Let's get back to our problem. Let's pretend that the message (m) we wish to encrypt and keep secret is only a single number, 4, to keep things easy. Let's get everything set up:

c = me mod n

c = 411 mod 701,111

c = 4,194,304 mod 701,111

We'll use an internet calculator to simplify the modulo process, but you're welcome to figure it out on your own. We get the following results by typing 4,194,304 into the online calculator:

c = 688,749

As a result, when we encrypt our message with RSA and our public key, we get a ciphertext of 688,749. The preceding steps may have appeared a little too math-heavy at first, but it's vital to remember what happened.

We had a four-message message that we intended to keep hidden. We used a public key to encrypt the result, which came out to 688,749. We can securely deliver the number 688,749 to the owner of the key pair now that it has been encrypted. With their private key, they will be the only ones who can decode it. They'll be able to view the message we were actually transmitting once they decrypt it.

Example:

1) The public and private keys of an RSA cryptosystem are generated by a specific A using two prime numbers, 13 and 17, respectively. If A's public is 35 people. Then A's private key is used. ……………?.

Solution:

Step 1: Choose two huge prime numbers, p and q, as the initial step.

p = 13

q = 17

Step 2: Multiply these integers to get n = p x q, where n is the encryption and decryption modulus.

First, we calculate

n = p x q

n = 13 x 17

n = 221

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (13 - 1) x (17 - 1)

φ (n) = 12 x 16

φ (n) = 192

g.c.d (35, 192) = 1

Step 4: We use the following formula to compute the d in order to determine the private key:

Calculate       d = de mod φ (n) = 1

d = d x 35 mod 192 = 1

d = (1 + k.φ (n))/e           [let k =0, 1, 2, 3………………]

Put k = 0

d = (1 + 0 x 192)/35

d = 1/35

Put k = 1

d = (1 + 1 x 192)/35

d = 193/35

Put k = 2

d = (1 + 2 x 192)/35

d = 385/35

d = 11

The private key is <d, n> = (11, 221)

Hence, private key i.e. d = 11

2) The public key is 3 and the private key is 7. In an RSA cryptosystem, the public key is 3 and the private key is 7. For a plain text, what is the value of cypher text?

Solution:

Step 1:  Choose two huge prime numbers, p and q, as the initial step.

p = 3

q = 13

Step 2: Multiply these integers to get n = p x q, where n is the encryption and decryption modulus.

We begin by calculating

n = p x q

n = 3 x 13

n = 39

Step 3: If n = p x q, then e, n> is the public key. The public key e, n> is used to encrypt a plaintext message m. As a result, the public key is e, n> = (3, 39).

To obtain ciphertext C from plain text, apply the formula below.

C = me mod n

C = 53 mod 39

C = 125 mod 39

C = 8

3) To create private key = 7, an RSA cryptosystem requires two prime numbers, 3 and 11. What is the value of ciphertext when using the RSA public-key encryption technique to encode plain text 5?

Solution:

Step 1: Choose two huge prime numbers, p and q, as the initial step.

p = 3

q = 11

Step 2: Multiply these integers to get n = p x q, where n is the encryption and decryption modulus.

We begin by calculating

n = p x q

n = 3 x 11

n = 33

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1< e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (3 - 1) x (11 - 1)

φ (n) = 2 x 10

φ (n) = 20

Step 4: We use the following formula to calculate the d in order to determine the public key:

Calculate e x d = 1 mod φ (n)

e x 7 = 1 mod 20

e x 7 = 1 mod 20

e = (1 + k. φ (n))/ d              [let k =0, 1, 2, 3………………]

Put k = 0

e = (1 + 0 x 20) / 7

e = 1/7

Put k = 1

e = (1 + 1 x 20) / 7

e = 21/7

e = 3

The public key is <e, n> = (3, 33)

Hence, public key i.e. e = 3

4.3 The equation Fermat's Last Theorem

Fermat's last theorem is a theorem that Fermat first proposed as a note scribbled in the margin of his copy of Diophantus' ancient Greek classic Arithmetical. The scrawled note was recovered after his death, and the original has since vanished. A copy, however, was preserved in a book written by Fermat's son. Fermat claimed in the memo that he had obtained proof that the Diophantine Equation was correct. Equation  has no integer solutions for  and .

The complete Latin wording of Fermat's remark is as follows: "Cubum autem in duos cubos, quadrato-quadratum in duos quadrato-quadratos, and generaliter nullam in infinity ultra quadratum potestatem in duos eiusdem nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi Non caperet hanc marginis exiguitas " (Nagell 1951, p. 252). In other words, "A cube cannot be the sum of two cubes, a fourth power cannot be the sum of two fourth powers, and any number bigger than the second cannot be the sum of two like powers in general. This thesis that this margin is too thin to contain has been demonstrated in an absolutely amazing way."

Fermat's marginal note resulted in the assertion that the Diophantine equation

 (1)

Where , , , and  are integers, has no nonzero solutions for  has Fermat's Last Theorem was named after him. On the strength of Fermat's remark, it was dubbed a "theorem," despite the fact that no other mathematician could verify it for hundreds of years. Note that the restriction  is obviously necessary since there are a number of elementary formulas for generating an infinite number of Pythagorean triples (x,y,z) satisfying the equation for ,

 (2)

An initial attempt to solve the equation can be performed by factoring the equation, which yields

 (3)

Since the product is an exact power,

 (4)

Solving for y and z gives

 (5)

Which give

 (6)

This strategy, however, does not provide any further information because solutions to these equations in rational numbers are no easier to obtain than answers to the original equation.

If an odd prime  divides , then the reduction

 (7)

Can be made, so redefining the arguments gives

 (8)

If no odd prime divides , then  is a power of 2, so  and, in this case, equations (7) and (8) work with 4 in place of . Since the case   was proved by Fermat to have no solutions, it is sufficient to prove Fermat's last theorem by considering odd prime powers only.

Similarly, is sufficient to prove Fermat's last theorem by considering only relatively prime x, y, and z, since each term in equation (1) can then be divided by , where  is the greatest common divisor.

The so-called "first case" of the theorem is for exponents which are relatively prime to ,, and  and was considered by Wieferich. Sophie Germain proved the first case of Fermat's Last Theorem for any odd prime  when  is also a prime. Legendre subsequently proved that if  is a prime such that ,, ,, or  is also a prime, then the first case of Fermat's Last Theorem holds for . This established Fermat's Last Theorem for . In 1849, Kummer proved it for all regular primes and composite numbers of which they are factors (Vandiver 1929, Ball and Coxeter 1987).

The "second case" of Fermat's last theorem is "  divides exactly one of  . Note that  is ruled out by  being relatively prime, and that if  divides two of  then it also divides the third, by equation (8).

Kummer's attack led to the theory of ideals, and Vandiver developed Vandiver's criteria for deciding if a given irregular prime satisfies the theorem. In 1852, Genocchi proved that the first case is true for  if ( is not an irregular pair. In 1858, Kummer showed that the first case is true if either (or ( is an irregular pair, which was subsequently extended to include ( and ( by Mirimanoff (1909). Although he argues Mirimanoff's proof of FLT for exponent 37 is still valid, Vandiver (1920ab) highlighted several gaps and mistakes in Kummer's memoir that, in his opinion, undermine Kummer's proof of Fermat's Last Theorem for the irregular primes 37, 59, and 67. Wieferich (1909) proved that if the equation is solved in integers relatively prime to an odd prime , then

 (9)

Ball and Coxeter (Ball and Coxeter, 1987). Wieferich primes are numbers that fall within this category. Mirimanoff (1909) later demonstrated that

 (10)

The first two Wieferich primes, 1093 and 3511, must also hold for solutions that are substantially prime to an odd prime. Vandiver made his debut in 1914.

 (11)

And Frobenius extended this to (12)

It has also been shown that if  were a prime of the form 6x-1, then

 (13)

Which raised the smallest possible  in the "first case" to 253747889 by 1941 (Rosser 1941). Granville and Monagan (1988) showed if there exists a prime  satisfying Fermat's Last Theorem, then

 (14)

For , 7, 11, ..., 71. This establishes that the first case is true for all prime exponents up to  (Vardi 1991).

The "second case" of Fermat's Last Theorem (for ) proved harder than the first case.

Euler proved the general case of the theorem for n=3, Fermat n=4, Dirichlet and Lagrange n=5. In 1832, Dirichlet established the case n=14. The n=7 case was proved by Lamé (1839; Wells 1986, p. 70), using the identity

 (15)

Although there were some mistakes in this proof, these were corrected by Lebesgue in 1840. Over the next 150 years, much more development was made, but no entirely general outcome was achieved. The mathematician Lindemann, buoyed by false confidence following his proof that pi is transcendental, went on to publish multiple proofs of Fermat's Last Theorem, all of which were erroneous (Bell 1937, pp. 464-465). A prize of German marks was also offered for the first valid proof, known as the Wolfskehl Prize (Ball and Coxeter 1987, p. 72; Barner 1997; Hoffman 1998, pp. 193-194 and 199).

Y. Miyaoka (Cipra 1988) raised a recent false alarm for a general proof, however his evidence was shown to be defective. Vos Savant (1993) discusses several attempted proofs by both professional and amateur mathematicians, however he incorrectly asserts that Wiles' work on the problem (covered below) is invalid. By the year 1993, the universal case of Fermat's Last Theorem had been demonstrated to be valid for all exponents up to infinity (Cipra 1993). Given that proving Fermat's Last Theorem necessitates truth for all exponents, proof for any finite number of exponents does not represent significant progress in proving the general theorem (although the fact that no counterexamples were found for this many cases is highly suggestive).

A bombshell was dropped in 1993. Andrew Wiles (Cipra 1993, Stewart 1993) partially proved the general theorem in that year by demonstrating the semistable instance of the Taniyama-Shimura conjecture. Unfortunately, Wiles' approach via the Taniyama-Shimura conjecture became hung up on properties of the Selmer group using a tool called an Euler system, and multiple errors in the proof were identified shortly after. Wiles and R. Taylor, however, solved the problem in late 1994 (Cipra 1994, 1995) and published Taylor and Wiles (1995) and Wiles (1995). (1995). Wiles' proof succeeds by (1) substituting Galois representations for elliptic curves, (2) reducing the problem to a class number formula, (3) establishing that formula, and (4) tying up loose ends that arise when the formalisms fail in the most basic degenerate circumstances (Cipra 1995).

Fermat's Last Theorem's proof symbolises the end of an era in mathematics. Given that practically all of the techniques that were subsequently used to solve the problem had not yet been devised at the time of Fermat, it's intriguing to hypothesise whether he had an elementary proof of the theorem. Fermat's stated proof appears to have been illusionary, based on the tenacity with which the problem eluded attack for so long. This conclusion is further supported by the fact that Fermat searched for proofs for the cases  and , which would have been superfluous had he actually been in possession of a general proof.

In the  episode of the television program The Simpsons, the equation  appeared at one point in the background. Expansion reveals that only the first 9 decimal digits match (Rogers 2005). The episode The Wizard of Evergreen Terrace mentions , which is correct not just in the first ten decimal places, but also in the last decimal place, which is easy to examine (Greenwald). Captain Picard says that learning Fermat's Last Theorem is a calming procedure in the Star Trek: The Next Generation episode "The Royale."

Key takeaways:

• Because there are no solutions to Fermat's equation, Fermat's Last Theorem is also true.

• It produces a semi-stable elliptic curve that cannot be modular but must be modular (Ribet's Theorem) (Wiles).

Numericals:

Q. Suppose that E(x) = 4x MOD 26. Determine the ciphertext alphabet.

Solution:

We begin with our table of numerical equivalents, and then determine 4x MOD 26.

Plain A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

4x 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 88 92 96 100

4x MOD 26 0 4 8 12 16 20 24 2 6 10 14 18 22 0 4 8 12 16 20 24 2 6 10 14 18 22

Cipher A E I M Q U Y C G K O S W A E I M Q U Y C G K O S W

The problem, of course, is that 4 and 26 are not relatively prime, and so this cyclic phenomenon occurs

In the cipher alphabet. Since the numbers 0, 2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, 24 are not relatively

Prime with respect to the 26, the only possible choices for the decimation cipher E(x) = ax MOD 26

Are a = 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25. Therefore, we conclude that the decimation cipher is weaker

Than the simple shift cipher. If the cryptanalyst knows that a shift cipher has been used, then there are

25 possible shifts that need to be checked.

Q. Show how we can encrypt plaintext 9 using the RSA public-key encryption algorithm. This example uses prime numbers 7 and 11 to generate the public and private keys.

Solution

Step 1: Select two large prime numbers, p, and q.

p = 7

q = 11

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for encryption and decryption.

First, we calculate

n = p x q

n = 7 x 11

n = 77

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (7 - 1) x (11 - 1)

φ (n) = 6 x 10

φ (n) = 60

Let us now choose relative prime e of 60 as 7.

Thus the public key is <e, n> = (7, 77)

Step 4: A plaintext message m is encrypted using public key <e, n>. To find ciphertext from the plain text following formula is used to get ciphertext C.

To find ciphertext from the plain text following formula is used to get ciphertext C.

C = me mod n

C = 97 mod 77

C = 37

Step 5: The private key is <d, n>. To determine the private key, we use the following formula d such that:

De mod {(p - 1) x (q - 1)} = 1

7d mod 60 = 1, which gives d = 43

The private key is <d, n> = (43, 77)

Step 6: A ciphertext message c is decrypted using private key <d, n>. To calculate plain text m from the ciphertext c following formula is used to get plain text m.

m = cd mod n

m = 3743 mod 77

m = 9

In this example, Plain text = 9 and the ciphertext = 37

Q. A RSA cryptosystem uses two prime numbers 3 and 13 to generate the public key= 3 and the private key = 7. What is the value of cipher text for a plain text?

Solution

Step 1: In the first step, select two large prime numbers, p and q.

p = 3

q = 13

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for encryption and decryption.

First, we calculate

n = p x q

n = 3 x 13

n = 39

Step 3: If n = p x q, then the public key is <e, n>. A plaintext message m is encrypted using public key <e, n>. Thus the public key is <e, n> = (3, 39).To find ciphertext from the plain text following formula is used to get ciphertext C.

C = me mod n

C = 53 mod 39

C = 125 mod 39

C = 8

Hence, the ciphertext generated from plain text, C = 8.

Q. A RSA cryptosystem uses two prime numbers, 3 and 11, to generate private key = 7. What is the value of ciphertext for a plain text 5 using the RSA public-key encryption algorithm?

Solution

Step 1: in the first step, select two large prime numbers, p and q.

p = 3

q = 11

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for encryption and decryption. First, we calculate

n = p x q

n = 3 x 11

n = 33

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e" such that 1< e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1. Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (3 - 1) x (11 - 1)

φ (n) = 2 x 10

φ (n) = 20

Step 4: To determine the public key, we use the following formula to calculate the d such that: Calculate e x d = 1 mod φ (n)

e x 7 = 1 mod 20

e x 7 = 1 mod 20

e = (1 + k. φ (n))/ d             

[let k =0, 1, 2, 3………………]

Put k = 0

e = (1 + 0 x 20) / 7

e = 1/7

Put k = 1

e = (1 + 1 x 20) / 7

e = 21/7

e = 3

The public key is <e, n> = (3, 33)

Hence, public key i.e. e = 3

Q. Given the public information [n, e] = [2599, 73], find the decrypt key d.

Solution

First, we must factor 2599 into its two prime factors. We find that 2599=23⋅113. We now determine that ϕ(2599)=ϕ(23)ϕ(113)=(22)(112)=2464. Now we want to solve the following linear congruence:

73d≡1(mod2464)

We can solve this linear congruence by finding a modular inverse of 73 (mod 2464) by the division algorithm as follows:

2464=73(33)+5573=55(1)+1855=18(3)+11=55+18(−3)1+55+[73+55(−1)](−3)1=73(−3)+55(4)1=73(−3)+[2464+73(−33)](4)1=2464(4)+73(−135)

Hence -135 can be used as a modular inverse. We thus get that:

(−135)73d≡(−135)1(mod2464)d≡−135(mod2464)d≡2329(mod2464)

Hence our decryption key d = 2329.

Q. Given the public information [n, e] = [2257, 997], find the decryption key d.

Solution

We will first factor 2257 into its two prime constituents. We note that 2257=37⋅61. We note calculate that ϕ(2257)=ϕ(37)ϕ(61)=(36)(60)=2160. We now want to solve the linear congruence 997d≡1(mod2160). We can do this by finding a modular inverse of 997 (mod 2160) by the division algorithm as follows:

2160=997(2)+166997=166(6)+11=997+166(−6)1=997+[2160+997(−2)](−6)1=2160(−6)+997(13)

Hence we can use 13 as an inverse to 997 (mod 2160). It hence follows that:

(13)997d≡(13)1(mod2160)d≡13(mod2160)

Hence our decrypt key d = 13.

Q. In an RSA cryptosystem, a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of A is 35. Then the private key of A is?

Solution

p = 13 and q = 17

Compute n = 13  imes 17 = 221 and phi = (13-1)  imes (17-1) = 12  imes 16 = 192 e = 35 (public key)

Compute d (private key)

a b d k

1 0 192 –

0 1 35 5

1 -5 17 2

-2 11 1 –

Therefore d = 11 (private key)

Q. Assume the message is encrypted by the function y = (11x + 4) MOD 26 (Encipher)

Solution:

To encrypt the plaintext MONEY, we first convert each letter in plaintext into a numerical value between 0 and 25 according to following list

A-0

B-1

C-2

D-3

.

.

.

Z-25

Thus, the numerical values corresponding to the plaintext MONEY are 12, 14, 13, 4, and 24.
Applying the given function for each numerical value, we have

M: y = (11*12 + 4) MOD 26 = 6
O: y = (11*14 + 4) MOD 26 = 2
N: y = (11*13 + 4) MOD 26 = 17
E : y = (11*4 + 4) MOD 26 = 22
Y : y = (11*24 + 4) MOD 26 = 8

The corresponding letters are GCRWI, which is the ciphertext.

(Decipher)

To decipher, we transform the function y as:
x = inverse (a) (y – b) MOD m
Then we have, x = inverse(11) (y – 4) MOD 26
Inverse(11) MOD 26 = 19, and the decryption function will be x = 19 (y – 4) MOD 26

We now decipher the ciphertext GCRWI by applying the decryption function. We have:

G: x = 19*(6-4) MOD 26 = 12
C: x = 19*(2-4) MOD 26 = 14
R: x = 19*(17-4) MOD 26 = 13
W: x = 19*(22-4) MOD 26 = 4
I: x = 19*(8-4) MOD 26 = 24

The corresponding plaintext letters are MONEY.