Asymmetric key algorithm - Revision history

Graham87: moved Asymmetric Algorithms to Asymmetric key algorithm over redirect: revert

2011-08-30T07:33:54Z

moved Asymmetric Algorithms to Asymmetric key algorithm over redirect: revert

← Previous revision	Revision as of 07:33, 30 August 2011
(No difference)

Graham87: moved Asymmetric key algorithm to Asymmetric Algorithms: history merge #2

2011-08-30T07:33:07Z

moved Asymmetric key algorithm to Asymmetric Algorithms: history merge #2

← Previous revision	Revision as of 07:33, 30 August 2011
(No difference)

Graham87: moved Asymmetric algorithm to Asymmetric key algorithm over redirect: revert

2011-08-30T07:26:14Z

moved Asymmetric algorithm to Asymmetric key algorithm over redirect: revert

← Previous revision	Revision as of 07:26, 30 August 2011
(No difference)

Graham87: 1 revision from :nost:Asymmetric algorithm: import old edit, see User:Graham87/Import

2011-08-30T07:25:59Z

1 revision from nost:Asymmetric algorithm: import old edit, see User:Graham87/Import

← Previous revision	Revision as of 07:25, 30 August 2011
(No difference)

Graham87: moved Asymmetric key algorithm to Asymmetric algorithm: history merge

2011-08-30T07:25:04Z

moved Asymmetric key algorithm to Asymmetric algorithm: history merge

← Previous revision	Revision as of 07:25, 30 August 2011
(No difference)

Ghakko: Redirecting to public-key cryptography.

2005-07-05T03:36:18Z

Redirecting to public-key cryptography.

← Previous revision		Revision as of 03:36, 5 July 2005
Line 1:		Line 1:
	~~'''Asymmetric key algorithm''' is a synonym for~~ [[public key cryptography]] ~~algorithm.~~		#REDIRECT [[public-key cryptography]]

DavidJablon: Consolidated into public key cryptography.

2005-07-05T01:45:35Z

Consolidated into public key cryptography.

← Previous revision		Revision as of 01:45, 5 July 2005
Line 1:		Line 1:
			'''Asymmetric key algorithm''' is a synonym for [[public key cryptography]] algorithm.
	In [[cryptography]], an '''asymmetric key [[algorithm]]''' uses a pair of [[cryptographic key]]s to encrypt and decrypt. The two keys are related mathematically; a message encrypted by the algorithm using one key can be decrypted by the same algorithm using the other. In a sense, one key "locks" a lock (encrypts); but a different key is required to unlock it (decrypt).

	==A postal analogy==
	An analogy which can be used to understand the advantages of an asymmetric system is to imagine two people, [[characters in cryptography\|Alice and Bob]], sending a secret message through the public mail. In this example, Alice has the secret message and wants to send it to Bob, after which Bob sends a secret reply.

	With a [[symmetric key algorithm\|symmetric key]] system, Alice first puts the secret message in a box, and then locks the box using a padlock to which she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he uses an identical copy of Alice's key (which he has somehow obtained previously, maybe by a face-to-face meeting) to open the box, and reads the message. Bob can then use the same padlock to send his secret reply.

	In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.
	The critical advantage in an asymmetric key system is that Bob and Alice never need send a copy of their keys to each other. This substantially reduces the chance that a third party (perhaps, in the example, a corrupt postal worker) will copy a key while it is in transit, allowing said third party to spy on all future messages sent between Alice and Bob. In addition, if Bob were to be careless and allow someone else to copy ''his'' key, Alice's messages to Bob will be compromised, but Alice's messages to other people would remain secret, since the other people would be providing different padlocks for Alice to use.

	==Actual algorithms -- two linked keys==
	Not all asymmetric key algorithms operate in precisely this fashion. The most common have the property that Alice and Bob each own ''two'' keys, one for encryption and one for decryption. In a secure asymmetric key encryption scheme, the decryption key should not be deducible from the encryption key. This is known as [[public-key cryptography]], since the encryption key can be published without compromising the security of encrypted messages. In the analogy above, Bob might publish instructions on how to make a lock ("public key"), but the lock is such that it is impossible (so far as is known) to deduce from these instructions how to make a key which will open that lock ("private key"). Those wishing to send messages to Bob use the public key to encrypt the message; Bob uses his private key to decrypt it.

	==Weaknesses==
	Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the [[one-time pad]] or its equivalents, there is no currently known asymmetric key algorithm which has been ''proven'' to be secure against a mathematical attack. That is, it is not known to be impossible that some relation between the keys in a key pair, or a weakness in an algorithm's operation, might be found which would allow decryption without either key, or using only the encryption key. The security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve. Such estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.

	This might not be as weak as imagined though. If an estimate of how long (by brute force) it takes to crack a code is say 1000 years then if it was used to encrypt your credit card details they would be perfectly safe – because the time to decrypt the details is longer than the useful life of those details (your credit card expires after a few years).

	Weaknesses have been found for promising asymmetric key algorithms in the past. The 'knapsack packing' algorithm was found to be insecure when an unsuspected attack came to light. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys. Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.

	Another potential weakness in the process of using asymmetric keys is the possibility of a '[[Man in the middle]]' attack, whereby the communication of public keys is intercepted by a third party and modified to provide the third party's own public keys instead. The encrypted response also must be intercepted, decrypted and re-encrypted using the correct public key in all instances however to avoid suspicion, making this attack difficult to implement in practice. The attack is not impossible, and an evil staff member at Alice or Bob's ISP might find it outright easy. This form of attack is being addressed by the development of [[key exchange\|key distribution]] methods that can ensure sender [[authentication\|authenticity]] and message [[data integrity\|integrity]], even over insecure channels.

	==History==
	The first known asymmetric key algorithm was invented by [[Clifford Cocks]] of [[GCHQ]] in the [[United Kingdom\|UK]]. It was not made public at the time, and was reinvented by [[Ron Rivest\|Rivest]], [[Adi Shamir\|Shamir]], and [[Len Adleman\|Adleman]] at [[Massachusetts Institute of Technology\|MIT]] in 1976. It is usually referred to as [[RSA]] as a result. RSA relies for its security on the difficulty of factoring very large integers. A breakthrough in that field would cause considerable problems for RSA's security. Currently, RSA is vulnerable to an attack by factoring the 'modulus' part of the public key, even when keys are properly chosen, for keys shorter than perhaps 700 bits. Most authorities suggest that 1024 bit keys will be secure for some time, barring a fundamental breakthrough in factoring practice, but others favor even longer keys.

	At least two other asymmetric algorithms were invented after the GCHQ work, but before the RSA publication. These were the [[Ralph Merkle puzzle cryptographic system]] and the [[Diffie-Hellman]] system. Well after RSA's publication, [[Taher Elgamal]] invented the [[Elgamal discrete log cryptosystem]] which relies on the difficulty of inverting logs in a finite field. It is used in the [[Secure Sockets Layer\|SSL]], [[Transport Layer Security\|TLS]], and [[DSA]] protocols.

	A relatively new addition to the class of asymmetric key algorithms is [[elliptic curve cryptography]]. While it is more complex computationally, many believe it to represent a more difficult mathematical problem than either the [[factorisation]] or [[discrete logarithm]] problems.

	==Practical limitations and hybrid [[cryptosystem]]s==
	One drawback of asymmetric key algorithms is that they are much slower (factors of 1000+ are typical) than comparably secure [[symmetric key algorithm]]s. In actual practice, both types are used, known as a [[hybrid cryptosystem]]. The receiver's public key encrypts a symmetric algorithm key which is used to encrypt the main message. This combines the virtues of both algorithm types when properly done.

	[[Category:Asymmetric-key cryptosystems]]

	[[de:Asymmetrischer Verschlüsselungsalgorithmus]]
	[[es:Criptografía asimétrica]]
	[[fr:Cryptographie asymétrique]]
	[[ja:公開鍵暗号]]
	[[pl:Kryptografia asymetryczna]]
	[[ru:Асимметричный шифр (криптосистема)]]

202.142.70.25: Added an example to the Symmetric Key Encryption Analogy (face-to-face meeting)

2005-06-21T12:23:43Z

Added an example to the Symmetric Key Encryption Analogy (face-to-face meeting)

← Previous revision		Revision as of 12:23, 21 June 2005
Line 4:		Line 4:
	An analogy which can be used to understand the advantages of an asymmetric system is to imagine two people, [[characters in cryptography\|Alice and Bob]], sending a secret message through the public mail. In this example, Alice has the secret message and wants to send it to Bob, after which Bob sends a secret reply.		An analogy which can be used to understand the advantages of an asymmetric system is to imagine two people, [[characters in cryptography\|Alice and Bob]], sending a secret message through the public mail. In this example, Alice has the secret message and wants to send it to Bob, after which Bob sends a secret reply.

	With a [[symmetric key algorithm\|symmetric key]] system, Alice first puts the secret message in a box, and then locks the box using a padlock to which she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he uses an identical copy of Alice's key (which he has somehow obtained previously) to open the box, and reads the message. Bob can then use the same padlock to send his secret reply.		With a [[symmetric key algorithm\|symmetric key]] system, Alice first puts the secret message in a box, and then locks the box using a padlock to which she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he uses an identical copy of Alice's key (which he has somehow obtained previously, maybe by a face-to-face meeting) to open the box, and reads the message. Bob can then use the same padlock to send his secret reply.

	In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.		In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.
Line 15:		Line 15:
	Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the [[one-time pad]] or its equivalents, there is no currently known asymmetric key algorithm which has been ''proven'' to be secure against a mathematical attack. That is, it is not known to be impossible that some relation between the keys in a key pair, or a weakness in an algorithm's operation, might be found which would allow decryption without either key, or using only the encryption key. The security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve. Such estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.		Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the [[one-time pad]] or its equivalents, there is no currently known asymmetric key algorithm which has been ''proven'' to be secure against a mathematical attack. That is, it is not known to be impossible that some relation between the keys in a key pair, or a weakness in an algorithm's operation, might be found which would allow decryption without either key, or using only the encryption key. The security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve. Such estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.

	This might not be as weak as imagined though. If an estimate of how long (by brute force) it takes to crack a code is say 1000 years then if it was used to encrypt your credit card details they would be perfectly safe – because the time to decrypt the details is longer than the useful life of those details (your credit card expires after a few years).		This might not be as weak as imagined though. If an estimate of how long (by brute force) it takes to crack a code is say 1000 years then if it was used to encrypt your credit card details they would be perfectly safe – because the time to decrypt the details is longer than the useful life of those details (your credit card expires after a few years).

	Weaknesses have been found for promising asymmetric key algorithms in the past. The 'knapsack packing' algorithm was found to be insecure when an unsuspected attack came to light. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys. Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.		Weaknesses have been found for promising asymmetric key algorithms in the past. The 'knapsack packing' algorithm was found to be insecure when an unsuspected attack came to light. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys. Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.

202.7.88.23: /* A postal analogy */

2005-06-17T01:07:07Z

A postal analogy

← Previous revision		Revision as of 01:07, 17 June 2005
Line 7:		Line 7:

	In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.		In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.
	The critical advantage in an asymmetric key system is that Bob and Alice never need send a copy of their keys to each other. This substantially reduces the chance that a third party (perhaps, in the example, a ~~corrupted~~ postal worker) will copy a key while it is in transit, allowing said third party to spy on all future messages sent between Alice and Bob. In addition, if Bob were to be careless and allow someone else to copy ''his'' key, Alice's messages to Bob will be compromised, but Alice's messages to other people would remain secret, since the other people would be providing different padlocks for Alice to use.		The critical advantage in an asymmetric key system is that Bob and Alice never need send a copy of their keys to each other. This substantially reduces the chance that a third party (perhaps, in the example, a corrupt postal worker) will copy a key while it is in transit, allowing said third party to spy on all future messages sent between Alice and Bob. In addition, if Bob were to be careless and allow someone else to copy ''his'' key, Alice's messages to Bob will be compromised, but Alice's messages to other people would remain secret, since the other people would be providing different padlocks for Alice to use.

	==Actual algorithms -- two linked keys==		==Actual algorithms -- two linked keys==

80.3.64.11: /* Weaknesses */

2005-05-28T11:19:00Z

Weaknesses

← Previous revision		Revision as of 11:19, 28 May 2005
Line 14:		Line 14:
	==Weaknesses==		==Weaknesses==
	Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the [[one-time pad]] or its equivalents, there is no currently known asymmetric key algorithm which has been ''proven'' to be secure against a mathematical attack. That is, it is not known to be impossible that some relation between the keys in a key pair, or a weakness in an algorithm's operation, might be found which would allow decryption without either key, or using only the encryption key. The security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve. Such estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.		Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the [[one-time pad]] or its equivalents, there is no currently known asymmetric key algorithm which has been ''proven'' to be secure against a mathematical attack. That is, it is not known to be impossible that some relation between the keys in a key pair, or a weakness in an algorithm's operation, might be found which would allow decryption without either key, or using only the encryption key. The security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve. Such estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.

			This might not be as weak as imagined though. If an estimate of how long (by brute force) it takes to crack a code is say 1000 years then if it was used to encrypt your credit card details they would be perfectly safe – because the time to decrypt the details is longer than the useful life of those details (your credit card expires after a few years).

	Weaknesses have been found for promising asymmetric key algorithms in the past. The 'knapsack packing' algorithm was found to be insecure when an unsuspected attack came to light. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys. Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.		Weaknesses have been found for promising asymmetric key algorithms in the past. The 'knapsack packing' algorithm was found to be insecure when an unsuspected attack came to light. Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys. Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.