Computing and Software Wiki - User contributions [en]

Public Key Encryption Algorithms

2008-04-12T22:34:34Z

Zhaoy36: /* How does Public Key Encryption work? */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|A message encrypted with a public key can only be decrypted by the corresponding private key]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===
[[Image:digital_signature.jpg|thumb|300px|right|The sender encrypts a message with his own private key. The receiver decrypts the message using the sender’s public key]]

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:29:06Z

Zhaoy36: /* Digital signature to ensure authenticity */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===
[[Image:digital_signature.jpg|thumb|300px|right|The sender encrypts a message with his own private key. The receiver decrypts the message using the sender’s public key]]

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:27:53Z

Zhaoy36: /* Digital signature to ensure authenticity */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===
[[Image:digital_signature.jpg|thumb|300px|right|The sender encrypts a message with his own private key which will be decrypted by the sender’s public key]]

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:27:02Z

Zhaoy36: /* Digital signature to ensure authenticity */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===
[[Image:digital_signature.jpg|thumb|300px|right|The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it]]

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:12:21Z

Zhaoy36: /* Digital signature to ensure authenticity */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===
[[Image:digital_signature.jpg|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:12:08Z

Zhaoy36: /* Digital signature to ensure authenticity */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===
[[Image:digital_signature.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

File:Digital signature.jpg

2008-04-12T22:10:28Z

Zhaoy36:

Public Key Encryption Algorithms

2008-04-12T22:08:58Z

Zhaoy36: /* Elliptic curve cryptography */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:08:24Z

Zhaoy36: /* A Working Example */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|The security of RSA is based on the difficulty of integer factorization]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:07:43Z

Zhaoy36: /* A Working Example */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===
[[Image:math_theory.gif|thumb|300px|right|Figure 1: Public Key Encryption]]
1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:07:30Z

Zhaoy36: /* Mathematical Theory */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:05:01Z

Zhaoy36: /* Mathematical Theory */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===
[[Image:math_theory.gif|thumb|300px|right|Figure 1: Public Key Encryption]]

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:04:21Z

Zhaoy36: /* Mathematical Theory */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

[[Image:math_theory.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

File:Math theory.gif

2008-04-12T22:03:28Z

Zhaoy36:

Public Key Encryption Algorithms

2008-04-12T22:02:06Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:01:41Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===
[[Image:pk_enc.gif|thumb|300px|right|Figure 1: Public Key Encryption]]
The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T22:01:27Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===
[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]
The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T21:59:08Z

Zhaoy36: /* How does Public Key Encryption work? */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

[[Image:pk_enc.gif|thumb|300px|center|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T21:57:51Z

Zhaoy36: /* How does Public Key Encryption work? */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

[[Image:pk_enc.gif|thumb|300px|right|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T21:55:34Z

Zhaoy36: /* How does Public Key Encryption work? */

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

[[Image:pk enc.jpg|thumb|300px|right|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-12T21:55:07Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[http://en.wikipedia.org/wiki/Public-key_cryptography R1]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

[[Image:pk_enc.jpg|thumb|300px|right|Figure 1: Public Key Encryption]]

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

File:Pk enc.gif

2008-04-12T21:51:11Z

Zhaoy36:

Public Key Encryption Algorithms

2008-04-05T21:49:10Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:43:50Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]
* [http://www.seas.harvard.edu/directory/professionalbio/index.html?id=2542u Dr. Rabin]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:37:19Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://www.certicom.com/index.php?action=ecc,res_home Certicom]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:35:01Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:28:09Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:28:00Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:27:48Z

Zhaoy36: /* See Also */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:27:33Z

Zhaoy36: /* References */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:27:16Z

Zhaoy36: /* Rabin cryptosystem */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:26:47Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:26:30Z

Zhaoy36: /* Efficiency */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:25:57Z

Zhaoy36: /* Rabin cryptosystem */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:25:49Z

Zhaoy36: /* Rabin cryptosystem */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem'''

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:24:40Z

Zhaoy36: /* Public Key Encryption */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:23:52Z

Zhaoy36: /* References */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.}

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:23:30Z

Zhaoy36: /* References */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

[R10] Rabin, MO (January 1979). "Digital signatures and public-key functions as intractable as factorization". {MIT Laboratory of Computer Science Technical Report.

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:22:14Z

Zhaoy36: /* Rabin cryptosystem */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization[R10].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:12:59Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.rsa.com/ RSA company]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:10:13Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.zvulony.com/ Zvuloney & Co]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-05T21:09:35Z

Zhaoy36: /* External Links */

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver[http://support.microsoft.com/kb/246071 R9].

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers[http://www.di-mgt.com.au/rsa_alg.html R6] :

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7], if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

[R9] Microsoft Help and Support. "Description of Symmetric and Asymmetric Encryption". Retrieved on 2008-04-05. http://support.microsoft.com/kb/246071

== See Also ==
[[Blowfish]] 
[[Digital Signatures]] 
[[Conventional Encryption Algorithms]] 
[[Digital Identity]] 

== External Links ==
* [http://www.zvulony.com/ Zvuloney & Co]
* [http://en.wikipedia.org/wiki/Wireless_community_network Wireless Community Networks]

--[[User:Zhaoy36|Zhaoy36]] 17:09, 5 April 2008 (EDT)

Public Key Encryption Algorithms

2008-04-04T06:00:50Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example[http://www.di-mgt.com.au/rsa_alg.html R6]. ===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7]., if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:58:59Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example[http://www.di-mgt.com.au/rsa_alg.html R6]. ===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7]., if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:57:14Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than symmetric cryptosystems.

===A Working Example[http://www.di-mgt.com.au/rsa_alg.html R6]. ===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields[http://en.wikipedia.org/wiki/Elliptic_curve_cryptography R7].

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization[http://en.wikipedia.org/wiki/Rabin_cryptosystem R8].

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

[R7] Wikipedia. "Elliptic curve cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

[R8] Wikipedia. "Rabin cryptosystem", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Rabin_cryptosystem

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:51:11Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames[http://en.wikipedia.org/wiki/RSA R5]. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than DES and other symmetric cryptosystems.

===A Working Example[http://www.di-mgt.com.au/rsa_alg.html R6]. ===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

[R5] Wikipedia. "RSA", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/RSA

[R6] DI Management, "RSA Algorithm", Retrieved on 2008-04-02. http://www.di-mgt.com.au/rsa_alg.html

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:43:29Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”[http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html R4]. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than DES and other symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

[R4] Charlie Fletcher. "Public Key Encryption". Retrieved on 2008-04-02.
http://www.krellinst.org/UCES/archive/modules/charlie/pke/node4.html

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:37:34Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1].

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than DES and other symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:36:32Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key[R2]. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it.

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than DES and other symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:33:12Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it.

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than DES and other symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Applied Cryptography, 2nd Ed, Bruce Schneier. ISBN: 0-471-11709-9 Publisher: Wiley

[R3] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

== See Also ==

== External Links ==

Public Key Encryption Algorithms

2008-04-04T05:27:28Z

Zhaoy36:

'''Public Key Encryption''' is also known as asymmetric cryptography[http://www.en.wikipedia.org/wiki/Public-key_cryptography R1]. It is widely used in protecting information transmission through unsecured communication channel. The famous public key encryption algorithms include RSA, ECC and Rabin Cryptosystems.

== Public Key Encryption==
=== How does Public Key Encryption work? ===

The user has a pair of keys - public key and private key. A message encrypted with a public key can only be decrypted by the corresponding private key. It is mathematically infeasible to derive private key from public key.

===Advantage over Symmetric Encryption===

Symmetric cryptography uses one key for both encryption and decryption. When the key is distributes to the sender and receiver, key may be leaked in the way.

Asymmetric encryption can protect information transmission through unsecured communication channel. Because it is mathematically infeasible to derive private key from public key, public key can be exposed to outside world. This prevents a third party from copying a key while it is in the way and further spying on the communication between sender and receiver.

===Digital signature to ensure authenticity===

The sender encrypts a message with his own private key. If the receiver can decrypt the sender’s message using the sender’s public key, this provides assurance that it is the sender (not a pretender) sent it.

===Mathematical Theory===

Many public key encryption algorithms are based on “Trap Door function”. Such type of function is easy to compute in one direction and difficult to calculate from the inverse direction. For example, f(x)=y is easy to compute y when x is given, but it is difficult to compute x when y is given.

== RSA ==
===What is RSA?===

RSA is a Public Key algorithm. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. It can be used to perform both signing and encryption.

===Mathematical Theory===

The security of RSA is based on the difficulty of integer factorization: Finding large primes and multiplying them together is easy. However, from the product to find the factors is hard. There is no known efficient general technique to solve this problem. However, due to recent progress in factoring integers, RSA public keys are recommended to be at least 1024 bits long to provide adequate security.

===Speed===

RSA is much slower than DES and other symmetric cryptosystems.

===A Working Example===

1. choose 2 prime numbers:

P=11, Q=3

2. compute N=P*Q:

N=11*3=33

3. compute L=(P-1)*(Q-1):

L= (11-1)*(3-1) = 10*2=20

4. choose E>1 and coprime to L:

Choose E=3

5. compute D such that E*D = 1 mod L:

D = 7 such that D*E =7*3 = 21 = 1 mod 20

6. public key is (N, E), private key is (N, D):

PK = (33, 3), SK= (33, 7)

7. Encrypt message using PK with C = M^E mod N:

Assume a message M=7, cipher text C = M^E mod N = 7^3 mod 33 = 343 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

== Elliptic curve cryptography ==
===What is ECC?===

Elliptic curve cryptography (ECC) is a public-key algorithm based on the algebraic structure of elliptic curves over finite fields.

===Mathematical Theory===

The security of Elliptic curve cryptography is based on the difficulty of solving discrete logarithm problem.

An elliptic curve has the following form:

y^2=x^3+ax+b.

The discrete logarithm problem on such elliptic curve groups is so difficult. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

===Efficiency===

Elliptic curves cryptography is more efficient with respect to key size.

Comparing with other public key algorithms, if the user wants 128-bit security, he needs a curve to create 256-bit key.
However, if the user chooses DSA, it would require 3072-bit public keys and 256-bit private keys. For RSA, it would require 3072-bit public and private keys.

== Rabin cryptosystem ==

'''Rabin Cyptosystem''' is a public key algorithm, whose security is also based on the difficulty of solving the problem of integer factorization.

For encryption, Rabin Cyptosystem is more efficient than RSA. For decryption, the efficiency of Rabin Cyptosystem is same as RSA.

Rabin system is more secure than RSA.

== References ==
[R1] Wikipedia. "Public-key cryptography", Wikipedia, 2008-04-02. Retrieved on 2008-04-02. http://en.wikipedia.org/wiki/Public-key_cryptography

[R2] Anoop MS (2007). Public key Cryptography - Applications Algorithms and Mathematical Explanations

== See Also ==

== External Links ==