Public Key Cryptography

written by: Bill Kuriko; article published: year 2007, month 05;



In: Categories » Computers and technology » Data security » Public Key Cryptography

In 1976, Diffie and Hellman proposed a new type of cryptography that distinguished between encipherment and decipherment keys. One of the keys would be publicly known; the other would be kept private by its owner. Classical cryptography requires the sender and recipient to share a common key. Public key cryptography does not. If the encipherment key is public, to send a secret message simply encipher the message with the recipient's public key. Then send it. The recipient can decipher it using his private key.

James Ellis, a cryptographer working for the British government's Communications-Electronics Security Group, said "he showed proof of concept in a January 1970 CESG report titled 'The Possibility of Secure Non-Secret Digital Encryption.'" Two of his colleagues found practical implementations. This work remained classified until 1997.

Because one key is public, and its complementary key must remain secret, a public key cryptosystem must meet the following three conditions.

  1. It must be computationally easy to encipher or decipher a message given the appropriate key.

  2. It must be computationally infeasible to derive the private key from the public key.

  3. It must be computationally infeasible to determine the private key from a chosen plaintext attack

The RSA cipher provides both secrecy and authentication.

RSA

RSA is an exponentiation cipher. Choose two large prime numbers p and q, and let n = pq. The totient ff(n) of n is the number of numbers less than n with no factors in common with n.

Our examples will use small numbers for pedagogical purposes. Actual RSA primes should be at least 512 bits each, giving a modulus of at least 1,024 bits. In practice, RSA is combined with cryptographic hash functions to prevent rearrangement of blocks.

EXAMPLE: Let n = 10. The numbers that are less than 10 and are relatively prime to (have no factors in common with) n are 1, 3, 7, and 9. Hence, ff(10) = 4. Similarly, if n = 21, the numbers that are relatively prime to n are 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20. So f(21) = 12.

Choose an integer e < n that is relatively prime to ff(n). Find a second integer d such that ed mod ff(n) = 1. The public key is (e, n), and the private key is d.

Let m be a message. Then:

c = m^e mod n

and

m = c^d mod n

EXAMPLE: Let p = 7 and q = 11. Then n = 77 and f(n) = 60. Alice chooses e = 17, so her private key is d = 53. In this cryptosystem, each plaintext character is represented by a number between 00 (A) and 25 (Z); 26 represents a blank. Bob wants to send Alice the message "HELLO WORLD." Using the representation above, the plaintext is 07 04 11 11 14 26 22 14 17 11 03. Using Alice's public key, the ciphertext is

07^17 mod 77 = 28

04^17 mod 77 = 16

11^17 mod 77 = 44

...

03^17 mod 77 = 75

or 28 16 44 44 42 38 22 42 19 44 75.

In addition to confidentiality, RSA can provide data and origin authentication. If Alice enciphers her message using her private key, anyone can read it, but if anyone alters it, the (altered) ciphertext cannot be deciphered correctly.

EXAMPLE: Suppose Alice wishes to send Bob the message "HELLO WORLD" in such a way that Bob will be sure that Alice sent it. She enciphers the message with her private key and sends it to Bob. As indicated above, the plaintext is represented as 07 04 11 11 14 26 22 14 17 11 03. Using Alice's private key, the ciphertext is

07^53 mod 77 = 35

04^53 mod 77 = 09

11^53 mod 77 = 44

...

03^53 mod 77 = 05

or 35 09 44 44 93 12 24 94 04 05. In addition to origin authenticity, Bob can be sure that no letters were altered.

Providing both confidentiality and authentication requires enciphering with the sender's private key and the recipient's public key.

EXAMPLE: Suppose Alice wishes to send Bob the message "HELLO WORLD" in confidence and authenticated. Again, assume that Alice's private key is 53. Take Bob's public key to be 37 (making his private key 13). The plaintext is represented as 07 04 11 11 14 26 22 14 17 11 03. The encipherment is

(07^53 mod 77)37 mod 77 = 07

(04^53 mod 77)37 mod 77 = 37

(11^53 mod 77)37 mod 77 = 44

...

(03^53 mod 77)37 mod 77 = 47

or 07 37 44 44 14 59 22 14 61 44 47.

The recipient uses the recipient's private key to decipher the message and the sender's public key to authenticate it.


EXAMPLE: Bob receives the ciphertext above, 07 37 44 44 14 59 22 14 61 44 47. The decipherment is

(07^13 mod 77)17 mod 77 = 07

(37^13 mod 77)17 mod 77 = 04

(44^13 mod 77)17 mod 77 = 11

...

(47^13 mod 77)17 mod 77 = 03

or 07 04 11 11 14 26 22 14 17 11 03. This corresponds to the message "HELLO WORLD" from the preceding example.

The use of a public key system provides a technical type of nonrepudiation of origin. The message is deciphered using Alice's public key. Because the public key is the inverse of the private key, only the private key could have enciphered the message. Because Alice is the only one who knows this private key, only she could have enciphered the message. The underlying assumption is that Alice's private key has not been compromised, and that the public key bearing her name really does belong to her.

In practice, no one would use blocks of the size presented here. The issue is that, even if n is very large, if one character per block is enciphered, RSA can be broken using the techniques used to break classical substitution ciphers. Furthermore, although no individual block can be altered without detection (because the attacker presumably does not have access to the private key), an attacker can rearrange blocks and change the meaning of the message.

EXAMPLE: A general sends a message to headquarters asking if the attack is on. Headquarters replies with the message "ON" enciphered using an RSA cipher with a 1,024-bit modulus, but each letter is enciphered separately. An attacker intercepts the message and swaps the order of the blocks. When the general deciphers the message, it will read "NO," the opposite of the original plaintext.

Moreover, if the attacker knows that headquarters will send one of two messages (here, "NO" or "ON"), the attacker can use a technique called "forward search" or "precomputation" to break the cipher. For this reason, plaintext is usually padded with random data to make up a block. This can eliminate the problem of forward searching, because the set of possible plaintexts becomes too large to precompute feasibly.

A different general sends the same request as in the example above. Again, headquarters replies with the message "ON" enciphered using an RSA cipher with a 1,024-bit modulus. Each letter is enciphered separately, but the first six bits of each block contain the number of the block, the next eight bits contain the character, and the remaining 1,010 bits contain random data. If the attacker rearranges the blocks, the general will detect that block 2 arrived before block 1 (as a result of the number in the first six bits) and rearrange them. The attacker also cannot precompute the blocks to determine which contains "O," because she would have to compute 21010 blocks, which is computationally infeasible.

legal disclaimer

1) Our website is not responsible for the information contained by this article as well for any and all copyright infringements by authors and writers. E-articles is a free information resource. If you suspect this article for any copyright infringements, please read the Terms of service and contact us to investigate the problem.
2) The E-articles directory team is not responsible for inaccuracies, falsehoods, or any other types of misinformation this tutorial may contain and will not be liable for any loss or damage suffered by a user through the user's reliance on the information gained here. Please read the Terms of service

Useful tools and features

Translate this article to...    Send this article to you or to a friend

Link to this article from your page   
If you like this article (tutorial), please link to it from your web page using the information above. Linking to this page, this is the only way to help us improve our service, the same time providing your visitors with a way to improve their online experience.

related articles

1. What are Buffer Overflows
Exploiting a buffer overflow is an advanced hacking technique. However, it is a leading type of security vulnerability. To understand how a hacker can use a buffer overflow to infiltrate or crash a computer, you need to understand exactly what a buffer is. A computer program consists of many different variables, or value holders. As a program is executed, these different variables are assigned a specific amount of memory as required by the type of information the variable is expected to hold. For example, a short integer ...

2. Protecting the Security of Information
The first and best line of defense against unwarranted intrusions into personal privacy is for individuals to employ e-commerce technology to protect themselves. Industry-developed and supplied encryption technologies and firewalls, for example, provide individuals with substantial tools to guard against unwarranted intrusions. Encryption is technology, in either hardware or software form, which scrambles e-mail, database information, and other computer data to keep them private. Using a sophisticated mathemati...

3. Why Is Authenticated SSL Necessary
Notions of identity and authentication are fundamental concepts in every marketplace. People and institutions need to get to know one another and establish trust before conducting business. In traditional commerce, people rely on physical credentials (such as a business license or letter of credit) to prove their identities and assure the other party of their ability to consummate a trade. In the age of e-business, authenticated SSL certificates provide crucial online identity and security to help establish trust between ...

4. Virus Prevention ~ How to protect against Internet Viruses
There are several elements to a good virus defense. The most important element requires some self-control—you must NEVER open a file/program unless you are 100% sure it is not infected. No matter how attractive the file is, where it came from, or what it promises you, you can never assume that a file is what it claims to be. For example, the Melissa virus reproduced through email and sent copies of itself to every one in the victim's address book. Because of this, relatives and friends of the victim were soon infected as ...

5. How to protect against Hostile Web Pages and Scripting
The dangers of Trojans and viruses are well known. However, many computer users are completely unaware of the dangers involved in viewing Web pages. Through scripting languages, Web page operators can upload and download files to your device (PC/PDA). They can also install mini-programs or grab information from you that can be used to destroy or take over your computer. Every time you go to a Web page, you actually download the full document to your computer. This includes all text, pictures, and even any code that is r...

6. Features of Windows Encrypting File System (EFS)
• Only available on Windows 2000 and Windows XP operating systems using NTFS partitions and volumes. (NTFS v5). • Encryption is transparent to the user. • Uses public-key encryption. Using a public key from the user’s certificate encrypts keys that are used to encrypt the file. The list of encrypted fileencryption keys is kept with the encrypted file and is unique to it. When decrypting the file encryption keys, the file owner provides a private key that only he has. ...

7. What are Denial of Service Attacks (DOS attacks) and how to protect against them
Hackers can wreak havoc without ever penetrating your system. For example, a hacker can effectively shut down your computer by flooding you with obnoxious signals or malicious code. This technique is known as a denial-of-service attack. Hackers execute a denial-of-service attack by using one of two possible methods. The first method is to flood the target computer or hardware device with information so that it becomes overwhelmed. The alternative method is to send a well-crafted command or piece of erroneous data that crash...