3.1 Philosophy of Public Key Cryptosystems (p-k Cryptography)

Public-key cryptography is a fundamental disappearance beginning the entire that has vanished by. From the ancient beginning 1960s to today’s complete cryptography is based on substitution and permutation [1]. It is also known by its other name asymmetric cryptography since it uses individual encryption key and another diverse except connected decryption key as shown in Figure 3.1.

Characteristics:

1. It is impracticable to decide the decryption key just get merely information procedure and the encryption key.

2. Among associated keys would be utilized for encryption, if one for encryption then other will be automatically decrypts it.

For any p-k process, the following are the basic main requirements.

1. Plain text: any readable information, i.e., provide for enter.
2. Encryption algorithm: for converting the plaintext.
3. Encryption and decryption keys: pairs of keys if one intended for making cipher, the further is for re-originating plain text. The precise changes executed by the procedure rely on keys offered like participation.
4. Cipher text: it is output in mess up form which relies on the puretext and key in support of same communication, with two dissimilar keys two disparate ciphers can be created.
5. Decryption algorithm: production of original message with the decryption key and cipher.

Note: Each key used has significance in p-k processing. Since Public key of a user A is available for world then it is used in encryption for secrecy and the same is used for decryption for authentication purposes. Whilst the private key seeded in decryption with both reasons: secrecy plus authentication as private hold only by owner.

In this, if only one of the authentication/confidentiality is considered then there would be chances to breach. Hence the pk process with aggregation of both gives the better unbreakable way. With the deeper into details consider Figure 3.2(a) in which we can see the opponent can easily determine message with the private key of receiver B. Also Figure 3.2(b) gives us the idea of beaching the authenticity as the text was arranged using A’s private key where A’s public key known by everyone so opponent can easily determine the private key of sender A. There it is decided in modern cryptography that p-k inbuilt both and secure the message by first encrypting by senders private key then again encrypt second time by the receivers public key, which brings confidentiality as seen in Figure 3.2(c). But this produces the complexity as the same algorithm processed four times [2, 3].

3.2 RSA Algorithm

It was given by Ron Rivest, Adi Shamir, and Len Adleman at MIT in 1978. The RSA is a chunk where the message and cipher are numbers from 0 to n − 1. RSA uses exponentials to encrypt the plain text into blocks having a binary value < n.

From ancient times, messages are encrypted using specific key to cipher text message. To regaining the message we need same key toward the mapping. Hence to communicate securely both sender and receiver both need to share the identical keys. On the way, sender has to share each identical key with each receiver and hence it has to manage the ring of identical keys to manage and also there would an extra overhead communication to share those keys. In 1970, James Alice gives a clever concept based on lock and unlocks which is inverse operation of each other. He said sender purchase a lock open it and send to receiver. On receiving the lock now the receiver lock it and send the message to sender where the sender can unlock it and read message, no keys were exchanged as seen in Figure 3.3(a). But in this opponent may also become a recipient and get the key. So it extended the concept by developing the keys inverse of each other [4]. The idea of inverse keys can be simplified by explaining with color mixing. The inverse of some color is the complementary color which one added to it produces white. Sender must randomly select an private key say red, next using the complementary color of red, i.e., cyan sends as an public key on non secured communication channel if an intruder traps then it gets cyan as shown in Figure 3.3(b). Let us say now receiver wants to send secret yellow so he mix it with cyan and form a new green which is sent back to sender, where intruders traps this green also. Now sender adds private color red to green and gets yellow which the receiver sent. So with the more advances Ron Rivest, Adi Shamir, and Len Adleman together gives an algorithm which is given in Table 3.1 fundamentally uses the prime factorization one way function which is quite hard to reverse and it takes hundreds of years to break. As such sender after computing all the x, y, n, Ф(n), e, and d sends only the n and e as a public key acting as an open lock where intruder traps n, e [5]. At receiver side, receiver locks by C, and sent back to sender so now the intruder trapped n, e, and C. But it must be notified that none can find the M without f(n) which requires prime factorization of n and which cannot be solved long years [6]. Illustration:

1. choose x = 11, y = 19
2. compute n = xy = 11 × 19 = 209
3. compute f(n) = (x − 1)(y − 1) = 180.
4. decide on e, relatively prime to and less than f(n), say e = 17.

5. establish d such that de = 1 (mod 180) and d < 180.
6. The accurate assessment for d is 77 as 77 × 17 = 1309 = 7 × 180 + 49 (using the extended version of Euclid’s algorithm)

3.3 Security Analysis of RSA

RSA obtains security by the complexity of factoring large numbers. Recuperating the message with single key and the cipher is two prime product factors. Therefore RSA can be break by the following attacks of determining the d while considering e and n.

1. Swine Force: Attempt finally probable keys. Typical protection is a bulky key to get better higher encryption key and decryption key.
2. Arithmetical attacks (trapdoor): Bifurgate the number n into two so permit computation of f(n) and the encryption key e = d⁻¹ (mod f(n)). The most excellent RSA algorithm is utilized to ratio n into:

This take much large years to break but new factorization methods also eases to this.

3. Time attacks: Kocher explained a novel assault on RSA where intruder know sender A hardware in enough feature moreover intelligent to determine the decryption period for frequent known ciphers, A can infer the d rapidly. This bother be functional beside the RSA. During Boneh and Brumley attacks over 2003 revealed a more sensible attack competent of recuperating RSA used in a system, e.g., by a Secure Socket Layer (SSL)-enabled web server. Such information is gained escaped by the CRT principle optimization taken by countless RSA accomplishments.

But new method of choosing r with sightless technique, the decryption period is nix lengthy correlated to the inputted cipher and so the timing attack is unsuccessful.

3.4 Exponentiation in Modular Arithmetic

In modular arithmetic, digits are by no means larger than the “modulus”. For instance, for “mod 12” digits are in no way superior than 11. The easiest technique to adapt digits in modular arithmetic is by separating at pleasing the remainder. Obtain 17/3. That is 5 with a remainder of 2, while it said “mod 17” that way that the intact phrase is modular, not presently the preceding number. Like is there would be an large multiplicative expression in modular arithmetic then before multiplication reduce into mod reduction and then solve this is the loveliness of modular arithmetic that the digits stay convenient.

1. Example: 12 * 29 * 408 mod 13
2. 12 mod 13 = 12
3. 29 mod 13 = 3
4. 408 mod 13 = 5
5. Solution: 12 * 3 = 36, but “mod 13” it is 10
6. Then 10 * 5 = 50 but “mod 13” that is 11, which is our answer.
7. →12 * 29 = 348 348 * 408 = 141,984 mod 13 = 11 so we get in above.

This is how a mod reduction can be applied.

However the exponentiation function and the logarithm function are reverse of each other which is a modular arithmetic. As we already discussed about the modular arithmetic in unit first so we do not repeat its details. The logarithm of any number is significant (except 1) that have to be lift so as to the same the integer. explicitly, for p and for q,

If we consider k = l (mod s) for some l, where 0 <l < (s − 1) then with the properties of logarithm we can discover a sole exponent as k = aⁱ(mod s) where 0 < i < (s − 1). So the discrete logarithm for the base a (mod s), which is dlog_a,s (k)¹⁰.

This can be seen as dlog _a,s (a) = 1 because a¹ mod s = a.

Fortunately with the previous example of 12 * 29 * 408 mod 13 it is already clear that proviso the exponentiation is ended above the integers plus next it must be condensed to modulo n, which is deducted as:

Example: watch M¹¹ = M¹⁺²⁺⁸ = (M)(M²)(M⁸). First calculate M mod n, M² mod n, M⁴ mod n, and M⁸ mod n and get [(M mod n) × (M² mod n) × (M⁸ mod n)] mod n.

In general, a^b would found with m positive integers where b is a binary number such that

Therefore

We can follow the algorithm to find for computing a^bmod n.

Solve itself: 37 * 10 mod 53; 5⁶ mod 23

3.5 Distribution of Public Keys

There are numerous method have been planned for the sharing of public keys in the history. Those proposals can be grouped into four.

A. Public announcement
Public key since announced publicly and it is an uncontrolled way of sending and sharing the key publicly. This can be easily forged, namely, various consumer might imagine user A to send a encryption key to a new member or transmit such a encryption key.

B. Publicly available directory.
More security is provided by upholding a publicly accessible active index keys though preservation with the sharing of the community directory would contain to be liable of have confident organization. The authority maintains each entry by {name, public key} which is registered to the participant in a secure way. It is much secure but still fails when an opponent thrive in attain or calculate the confidential key of the index influence, the opponent might confidently passing the imitation public keys and snoop on post propel to any member an additional approach to reach the similar ending at challenger tampering influencing with account.

Example: Modular Exponentiation Algorithm for ab mod n, where a = 7, b = 560 = 1000110000, and n = 561.

C. Public-key authority
Since every contributor consistently knows a public key for the authority, by means of merely the authority meaningful the matching private key, the sharing of public keys commencing the directory is strongly controlled. However it is not safe as a user have to plea to the authority for a public key for each further user so as to it needs to call. Moreover the index of names in addition to public keys preserve by the authority is susceptible to tampering.

D. Public-key certificates
An unconventional loom where the participants uses certificates to swap keys devoid of drop a line to a public-key authority demonstrated in Figure 3.4. Certification authority (CA) attach public key to picky participant P, i.e., P (person, router) list its public key with CA by only if “proof of identity” to CA and CA generate certificate attaching P to its public key. This credential hold P’s public key digitally marked by CA or CA says “this is E’s public key”.

Thereafter, certificate authority generated the certificates, which are known by the applicant with the corresponding confidential key. A contributor broadcasts its credential to express its entered information and other participants can validate that the certificate was shaped by the ability. Here certificate authority (CA) configures the entire nodes. When participant A wants participant B’s public key it gets B’s certificate and apply CA’s public key to B’s certificate, so what verifying B’s public key which has been demonstrated mathematically in Figure 3.5.

1. 1. Blake, I., Seroussi, G., Smart, N., Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, 1999.
2. 2. Enge, A., Elliptic Curves and Their Applications to Cryptography, Kluwer Academic Publishers, Norwell, MA, 1999.
3. 3. Diffie, W., The First Ten Years of Public-Key Cryptography. Proc. IEEE, Vol. 76, pp. 560–577, 1988.
4. 4. Rosen, K., Elementary Number Theory and its Applications, Addison-Wesley, Reading, MA, 2000.
5. 5. Kumanduri, R. and Romero, C., Number Theory with Computer Applications, Prentice Hall, Upper Saddle River, NJ, 1998.
6. 6. Boneh, D., Twenty Years of Attacks on the RSA Cryptosystem. Not. Am. Math. Soc., vol. 46, 2, pp. 203–213, 1999.
7. 7. Cormen, T., Leiserson, C., Rivest, R., Stein, C., Introduction to Algorithms, MIT Press, Cambridge, index MA, 2004.
8. 8. Shamir, A. and Tromer, E., On the Cost of Factoring RSA-1024. Crypto RSA-1024, RSA CryptoBytes, Vol. 6, pp. 10–19, 2003. http://www.rsasecurity.com/rsalabs.
9. 9. Stallings, W., Cryptography and network security principles and practice, fifth edition, Pearson Education, Inc., publishing as Prentice Hall, Upper SaddleRver, NJ, 2006.
10. 10. Diffie, W., Hellman, M.E., New Directions in Cryptography, IEEE Transactions on Information Theory, Vol. 22, 6, pp. 644–654, 1976.