articles 13,14

Cryptography

The expansion of the connectivity of computers makes ways of protecting data and messages from tampering or reading important. Even the US courts have ruled that there exists no legal expectation of privacy for email. It is thus up to the user to ensure that communications which are expected to remain private actually do so. One of the techniques for ensuring privacy of files and communications is Cryptography. Instead sending the data as it is, we encrypt the data according to some algorithm and send it to the destination. If the receiver is authorized then only he will be able to decrypt it back following by some techniques. This is how we can optimize the network security to some extent.

RSA Algorithm

The RSA algorithm was first published in the paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems in 1977 by Ron Rivest, Adi Shamir and Len Adleman. It is named after the initials of their surnames. The paper was published in the September 1977 issue of The Scientific American. The authors offered to send their full report to anyone who sent them a self-addressed stamped envelope. The NSA did not like the idea of distributing the cryptography source code internationally and requested that it be stopped. However the distribution continued when the NSA failed to provide a legal basis for their request. The algorithm was published in The Communications of the ACM the following year.

Key Generation Algorithm

1. Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits.
2. Compute n = pq and (φ) phi = (p-1)(q-1).
3. Choose an integer e, 1 <>
4. Compute the secret exponent d, 1 <>
5. The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret.

• n is known as the modulus.
• e is known as the public exponent or encryption exponent.
• d is known as the secret exponent or decryption exponent.

Encryption

Sender A does the following:-

1. Obtains the recipient B's public key (n, e).
2. Represents the plaintext message as a positive integer m [see note 4].
3. Computes the ciphertext c = m^{^e} mod n.
4. Sends the ciphertext c to B.

Decryption

Receiver B does the following:-

1. Uses his private key (n, d) to compute m = c^{^d} mod n.
2. Extracts the plaintext from the integer representative m.

Digital signing

Sender A does the following:-

1. Creates a message digest of the information to be sent.
2. Represents this digest as an integer m between 0 and n-1.
3. Uses her private key (n, d) to compute the signature s = m^{^d} mod n.
4. Sends this signature s to the recipient, B.

Signature verification

Receiver B does the following:-

1. Uses sender A's public key (n, e) to compute integer v = s^{^e} mod n.
2. Extracts the message digest from this integer.
3. Independently computes the message digest of the information that has been signed.
4. If both message digests are identical, the signature is valid.

Block Diagram of various encryption/decryption operations in RSA

A simple example:

This is an extremely simple example and would not be secure using primes so small, normally the primes p and q would be much larger.

1. Select the prime integers q=11, q=3.
2. n=pq=33; φ(n)=(p-1)(q-1)=20
3. Choose e=3
• Check gcd(3,20)=1
4. Compute d=7
• (3)d ≡ 1 (mod 20)

Therefore the public key is (n, e) = (33, 3) and the private key is (n, d) = (33, 7).

Now say we wanted to encrypt the message M=7

• C = M^e mod n
• C = 7³ mod 33
• C = 343 mod 33
• C = 13

So now the cyphertext C has been found. The decryption of C is performed as follows.

• M' = C^d mod n
• M' = 13⁷ mod 33
• M' = 62,748,517 mod 33
• M' = 7

As you can see after the message has been encrypted and decrypted the final message M' is the same as the original message M. A more practical way to use the algorithm is to convert the message to hexadecimal and perform the encryption and decryption steps on each octet individually.

CONTRIBUTED BY: Sundargopal Sarkar (III B.Sc. CS)

COMPUTER PUZZLE

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

Clues

1. Short form of multiplexer (3)

2. B is a ___________ based language (2)

3. Developer of C (7).

4. User defined data types are defined using the keyword ___(7)

5. Standard O/P stream in C++ (4)

6. Standard I/P stream in C++ (3)

7. ______ is an abstraction that refers to a few data (6)

8. Father of computer (7)

9. C was developed at AT & T ____ laboratories (4)

10. Powerful set of statements which repeats again & again till the conditions are met (4)

11. Developer of language B (8)

12. C works on ____ operating system (4)

13. C is a ______ language (7)

14. Comes under a type in semiconductor memory (of primary memory) (3)

15 ______ 67 gives C++ all the construct features of OOPS (6)

ANSWERS

CONTRIBUTED BY:M.Vikram Kumar (III B.C.A. Evening)