Question

Answer digital signatures question. assume Alice has the RSA key (eA, dA, nA) and Bob has the RSA key(eB, dB, nB), where eA, eB, nA, and nB are public, dA is known only to Alice, and dB is known only to Bob.

(a) Describe how Alice could use her RSA key to sign a public message m, and explain why this approach satisfies the objective of non repudiation.

(b) Describe how Alice could encrypt and send a secret message to Bob in such a way that only he could read it, and he would be convinced the message came from Alice.

Answer 1

RSA is a public key crypto system. Its security depends on the assumption that in the current state of computer technology, the factorization of composite numbers with large prime factors is prohibitively time consuming.

(a) Each user of RSA system chooses a pair of distinct primes, p and q, large enough that the factorization of their product n=pq, is beyond all computational capabilities. The product n=pq, is called enciphering modulus. Having selected n, the user then chooses a random positive integer k, satisfying . The integer k is called the enciphering exponent. Although there ara many suitable choices for k, an obvious suggestion is to pick k to be any prime larger than both p ad q.The pair (n,k) (ie., public key) is then placed in a public file as the user's personal encryption key. This allows anyone else in the communication network to encrypt and send a message to that individual.

(b) The encryption process begins with the conversion of the message to be sent into an integer M by means of a "digital alphabet" in which each letter, number or punctuation mark of the plain text is replaced by a two digit integer. One standard procedure is to use the following assignment:

A=00 B=01 C=02 D=03 E=04 F=05 G=06 H=07 I=08 J=09 K=10

L=11 M=12 N=13 O=14 P=15 Q=16 R=17 S=18 T=19 U=20

V=21 W=22 X=23 Y=24 Z=25

=26 =27 ?=28

0=29 1=30 2=31 3=32 4=33 5=34 6=35 7=36 8=37 9=38

1!=39

99- indicate space between words

It is assumed that plain text number , the enciphering modulus. When the message is too long to be handled as a single number , then is broken up into blocks of digits of appropriate sizes. Each block is encrypted separately,

With the help of recipients' encryption key , the sender converts the plain text number to a cipher text number by using the relation

Now the recipient first determine an integer for which  .

The integer is called recovery exponent. Since , the above congruence has a unique solution modulo . The recovery exponent can be calculated by someone who knows both and prime factors and  . Then only he can calculate .

Thus is secure from a third party whose knowledge is limited to the public key .

The recipient can simply retrieve   from   by simply calculating  

(since if   then by Euler theorem )

If then using a similar argument we can prove that   and   which yields ie.,

The major advantage of RSA system is that the encryption of a message does not require the knowledge of the two primes in advance. There is no need for any one other than the receiver of the message to know the prime factors which are critical to the decryption process.