Congruency

Two integers a and b are said to be congruent (mod n), written a ≡ b, if a = b + nm for
some integer n. For example, 25 ≡ 17 ≡ 1(mod 4), thus, two integers are congruent if
they both have the same remainder when divided by n. We can say a ≡ b(mod n) if n
divides evenly into (a – b). If a and n have no common factors, they are said to be relatively
prime and then the congruency ax ≡ 1(mod n) always has a unique solution.
Algorithms have to be found to satisfy all three criteria. One is the RSA algorithm.
The method is based on number theory and can be summarized as follows:
1. Choose two large primes, p and q, (typically > 10100).
2. Compute n = p × q and z = (p-1) × (q-1).
3. Choose a number relatively prime to z and call it d.
4. Find e such that e × d = 1 mod z.
To apply the algorithm, we divide the plaintext (bit strings) into blocks so that each
plaintext message, P, falls in the interval O ≤ P < n. This can be done by grouping the
plaintext into blocks of k bits, where k is the largest integer for which 2k < n is true.
 To encrypt a message, P, compute C = Pe(mod n).
 To decrypt the message, C, compute P = Cd(mod n).
 To perform encryption, e and n are needed.
 To perform decryption, d and n are needed.
 Therefore, e, n are the public keys and d is the private key.
The security of the method is based on the factoring of large numbers. If n can be factored,
p and q can be found, and from these, z. From z and e, d can be found. However,
factoring large numbers is immensely difficult. According to Rivest, Shamir, and Adelman,
factoring a 200-digit number requires 4 billion years of computer time. A 500-
digit number requires 1025 years. In both cases, the best-known algorithm is assumed
and a 1 μs instruction time. On this basis, if computers get faster by an order of magnitude
per decade, centuries are still required to factor a 500-digit number.
An example will demonstrate the calculations. We will use small numbers:
p = 3 and q = 11 is chosen.
n = p × q, so, n = 3 × 11 = 33.
z = (p – 1) × (q – 1), so z = (3 – 1) × (11 – 1) = 20.

A suitable value for d is 7, as 7 and 20 have no common factors, and e can be found
by solving:
de = 1 (mod z)
∴ = 1 (mod 20)
∴ = 1 (mod 20)/7
= 3
The ciphertext, C, for a plaintext message, P, is given by C = Pe (mod n); that is, C =
P3(mod 33). The ciphertext is decrypted by the recipient according to the rule P =
Cd(mod 33).
Atest case using the word ROGER will demonstrate (see Table 9.6). As the primes chosen
for this example are very small, P must be less than 33, so each plaintext block can
only be a single character. The result will therefore be a mono-alphabetic substitution
cipher—not very impressive. If p and q ≈ 10100, n would equal 10200, and each block could
be up to 664 bits or eighty-three 8-bit characters. The procedure can be followed:
Encrypt R = This is the 18th letter in the alphabet.
This letter will be called plaintext P.
So, P = 18.
P3 = 5832.
Ciphertext (C) = P3 (mod n).
= 5832 (mod 33).
To find Pe (mod 33):
5832/33 = 176.7272727.
So, C = 33 × 0.7272727 = 24.
So, for the letter R, 24 is transmitted and the numeric value 24 is received.
The recipient calculates Cd = 247 = 4586471424.
and then Cd(mod n) = 4586471424 (mod 33).
to find Cd(mod n): 4586471424 = 138983982.545454.
So, the numeric value of the symbol = n × 0.545454 = 18 (that is, the letter R).

RSA is widely used as a public key algorithm but is considered too slow for processing
large amounts of data. The Weizmann Institute Key Locating Engine (Twinkle)
is an electro-optical computer designed to execute sieve-based factoring algorithms
approximately two to three orders of magnitude faster than a conventional fast PC.
Designed by Professor Adi Shamir (of RSA), it should crack 512-bit RSA keys in a few
days, according to Shamir.
Presently, a rough design, it should run at 10 GHz and uses wafer scale integration
(source: New Electronics, Sept 99).