This page is obsolete please click here to jump to the updated website


RSA Algorithm (Rivest Shamir Adleman)

The RSA algorithm is named after the 3 MIT researchers that developed it in 1978. (Ronald Rivest, Adi Shamir e Leonard Adleman).
The cryptographic telephone applications developed by Kryptotel use this algorithm together with the AES to enable the encryption on the Iphone, the fixed telephone and for the applications that are installed on the PC.

With the development of electronic devices (smartphone, smart card, token and PC) the application of the algorithm has become of vital importance to guarantee secrecy, authentication and protection of the information that goes through or that is stored in the devices. The disadvantage of using a private key algorithm (symmetric cryptography) is that it involves the use of only one encryption and decryption key. In order to be used the key has to be exchanged between the sender and the recipient and it is during this exchange that the Key can be intercepted. In 1976 two cryptologist's, Diffie and Hellman, were inspired by the limitations that symmetric algorithms had, and they introduced a new approach to cryptography, by assuming that the only way to overcome the limitations was by using two distinct keys for the data encryption and decryption. The advantage is that the decrypting key, also called private key, can be sent using insecure communication methods while the private key used for the encryption operations is safely stored by its owner.

Many attempts were made to create an algorithm that would succeed by following this theory. The first algorithm that was able to embrace this approach was discovered in 1978, and it was exactly the RSA, the most used and efficient algorithm used to this day. The RSA cipher represented a real turning point for practical applications with high quality, guaranteed security and reliability. In fact the expression strong encryption was invented exactly with the RSA algorithm.

Features of the RSA algorithm

Following are the main features of the algorithm:

  • secrecy and privacy: the content of the information and communication must be ONLY accessible to the sender and the recipient of the information
  • integrity: the content must not be altered during the exchange phase, therefor it must stay in its original form
  • authentication: this aspect is very important because RSA guarantees the origin of the sent information, only the sender with his own private key is able to encrypt the message therefor transform the message into an unreadable form consequently the receiver will have confirmation of the origin because he will be able to decrypt the message only through the corresponding public key
  • non repudiation: the sender cannot state that the message has not been encrypted with his private key because the private key used for the encryption is unique and it's the owner's responsibility to make sure that it is not used by non authorized third parties

Practical applications of the RSA algorithm

To this day the RSA together with the AES algorithm is the most used algorithm in commercial systems.
It is used:
-to protect web traffic, in the SSL protocol (Security Socket Layer),
-to guarantee email privacy and authenticity in PGP (Pretty Good Privacy)
-to guarantee remote connection in SSH (Secure Shell).
-Furthermore it plays an important role in the modern payment systems through SET protocol (Secure Electronic Transaction).

RSA has been used in most digital data, information and telephone security applications.

The RSA has it's advantages of being a reliable and safe system but it also has the disadvantage of being very slow in data calculating. For this reason it is used in hybrid cryptographic systems that simultaneously use symmetric algorithms (AES) for the communication and data encryption phase and public key algorithms (RSA) for the safe delivery of the symmetric key (or session key) that is necessary for encrypting and decrypting the message. There are different levels of encryption in telephone cryptography. The same approach has been adopted by Kryptotel for information security solutions and for mobile and fixed telephone lines that cannot be intercepted.

Following is a graphic example of one of Kryptotel's solutions with the RSA algorithm:

RSA - Encryption process

RSA - Decryption process

RSA_descriptionprocess

Traceability of the private key starting with the public key

The stability of an asymmetric algorithm depends on mathematics and on the algorithms used for the construction of the communication or encrypted message. The inability or computational complexity arising from the calculation of the private key from the public key is strictly related to the resolution of a complex mathematical problem; for example factoring "large" numbers (the concept of "large" numbers is of course relative, and depends on the evolution capabilities of the calculating power of the processors). To this day a large number, in cryptography, is a number of 200 plus digits. In most cryptographic systems security is entrusted by large number factoring and to this day an efficient algorithm does not exist; meaning an algorithm that is able to respond in reasonable amounts of time and that is able to factor a large number in prime numbers. Until an efficient algorithm for large number factoring is discovered cryptographic systems based on these techniques will be very safe. Especially because quantum computers that are able to increase calculating power do not exist.

 

Technical details

Key generation

  1. Choosing two Interger numbers:
    q = 11, q = 3.    
  2. n = pq = (11)(3) = 33
    calculate f (n) = (p-1) (q-1) = 20
  3. Choose e = 3 and calculate MCD(e, p-1) = MCD(3,20) = 1  (3 and 10 do not have common factors apart from 1) 
    calculate MCD(e, q-1) = MCD(3,2) = 1,  
    and MCD(e, f(n)) = MCD(e, (p-1)(q-1)) = MCD(3,20) ≡ 1 (mod 20)  = 1
  4. Calcuate d so that ed=(mod f(n))
    for example assume that d = e-1 mod f(n) = 3-1 mod 20
  5. Therefor the public key is (n, e) = (33, 3) and
    the private key is (n, d) = (33, 7).
    Encryption
    The encrypted text C is obtained from the equation 'C = n mod Me', where M is the original message.
    Decryption
    The M message can be recreated by decrypting the encrypted C text from the equation 'M = n mod Cd'.