Ma3626 - find the number of possible encryption exponents

Question

Question 1. You encrypt a message using the RSA encryption system as t^e mod n, where t, e < n and t is the numerical equivalent of the message. The message is written in a 27-letter alphabet and is split into blocks with m characters each. You have a limit of 10¹² binary operations to encrypt each block. Estimate the largest possible value of m if you use the fast exponentiation algorithm and

(a) standard algorithms for division and multiplication, which we assume require 100 .log₂a.log₂b binary operation to find ab and to find the quotient and remainder when a is divided by b;

(b) the best known algorithms for division and multiplication, which we assume for a ≥ b require

100.(log₂a).(log₂ log₂).(log₂ log₂log₂ a)

binary operation to find ab and to find the quotient and remainder when a is divided by b.

Remark. You may assume that the number of operations in the fast exponentiation algorithm is twice more than the number of operations needed for all squarings.

The number of operations needed to convert the message into a number is small and can be ignored. You may also ignore the difference between n and φ(n).

In part (b) you have to solve a transcendental equation. During the calculations you can round the results of iterations to the nearest integer.

Question 2. You intercept the ciphertext message

SJTJIPQJGAIZ

which you know was encrypted using an affine map on digraphs in the 26-letter alphabet, where a digraph whose two letters have numerical equivalent x and y corresponds to 26x + y. The statistical analysis of earlier ciphertexts which had been coded by the same enciphering map shows that the most frequently occurring digraphs are RA and WL in that order. It is known that the most common digraphs in English are TH and HE in that order. Find the deciphering transform and read the message.

Question 3. (a) Break the RSA code whose enciphering key is

(n, e) = (633262111, 1000001).

Find the deciphering map and then decipher the message

AGSGKWKACBFVNQ

under the assumption that the plaintext consists of 6-letter blocks in a 27-letter alphabet (A -Z have usual numerical equivalents 0- 25 and blank = 26), converted to an integer between 0 and 276_1 in the usual way, and the ciphertext consists of 7-letter blocks in the same alphabet.

(b) Find the number of possible encryption exponents e < φ(m) for the above value of m.

(c) Suppose you use RSA with m = 59768553302699443. You choose to split the plainetext and ciphertext written in the above al-phabet with 27 characters into blocks with k and in characters respectively. Find the largest possible value of k and the smallest possible value of in.