P2Pprogrammer 2 programmer

Home > Tips > Encryption and Decryption > Asymmetric Encryption

Asymmetric Encryption

Asymmetric Encryption, Public Key Cryptography, RSA signatures, Asymmetric Encryption Source Code , Download .NET Encryption Source Code

What is Asymmetric Encryption?
Asymmetric Encryption is a form of Encryption where keys come in pairs. What one key encrypts, only the other can decrypt. Frequently (but not necessarily), the keys are interchangeable, in the sense that if key A encrypts a message, then B can decrypt it, and if key B encrypts a message, then key A can decrypt it. While common, this property is not essential to asymmetric encryption.

Asymmetric Encryption is also known as Public Key Cryptography, since users typically create a matching key pair, and make one public while keeping the other secret.

Users can "sign" messages by encrypting them with their private keys. This is effective since any message recipient can verify that the user's public key can decrypt the message, and thus prove that the user's secret key was used to encrypt it. If the user's secret key is, in fact, secret, then it follows that the user, and not some impostor, really sent the message.

Users can send secret messages by encrypting a message with the recipient's public key. In this case, only the intended recipient can decrypt the message, since only that user should have access to the required secret key.

The key to successful use of Asymmetric Encryption is a Key Management system, which implements a Public Key Infrastructure. Without this, it is difficult to establish the reliability of public keys, or even to conveniently find suitable ones.

History of Asymmetric or Public Key Encryption

The first invention of asymmetric key algorithms was by James H. Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ in the UK in the early 1970s; these inventions were what later became known as Diffie-Hellman key exchange, and a special case of RSA. The GCHQ cryptographers referred to the technique as "non-secret encryption". These inventions were not publicly disclosed at the time, and the fact that they had been developed was kept secret until 1997.

An asymmetric-key cryptosystem was published in 1976 by Whitfield Diffie and Martin Hellman, who, influenced by Ralph Merkle's work on public-key distribution, disclosed a method of public-key agreement. This method of exponential-key exchange, which came to be known as Diffie-Hellman key exchange, was the first published practical method for establishing a shared secret-key over an unprotected communications channel without using a prior shared secret. Merkle's public-key-agreement technique became known as Merkle's Puzzles, and was published in 1978.

A generalisation of the Cocks method was reinvented in 1977 by Rivest, Shamir and Adleman, all then at MIT. The latter authors published their work in 1978, and the algorithm appropriately came to be known as RSA. RSA uses exponentiation modulo a product of two large primes to encrypt and decrypt, performing both public key encryption and public key digital signature, and its security is connected to the presumed difficulty of factoring large integers, a problem for which there is no known efficient (i.e., practicably fast) general technique.

Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public-key cryptography. The ElGamal cryptosystem (invented by Taher ElGamal then of Netscape) relies on the (similar, and related) difficulty of the discrete logarithm problem, as does the closely related DSA developed by the NSA and NIST. The introduction of elliptic curve cryptography by Neal Koblitz in the mid 1980s has yielded a new family of analogous public-key algorithms. Although mathematically more complex, elliptic curves appear to provide a more efficient way to leverage the discrete logarithm problem, particularly with respect to key size.

Examples of Public-Key Cryptosystems
1. Merkle's Puzzles
Merkle's Puzzles was one of the first public key cryptographic systems to be described. It allows principals A and B to agree on a secret key. Principal A invents a million keys and a million puzzles, where each puzzle encodes a different one of the keys. Each puzzle is assumed to take at least two minutes to solve and to fit into 96 bits. A sends these puzzles to B. B then picks a puzzle at random and solves it. B encrypts a pre-arranged string (say 0000) with the key from the puzzle it solved. B sends this encrypted string back to A. A tries each of the million keys on the message it receives from B. The one that decrypts the message and obtains the pre-arranged string is the shared key that A will use henceforth to communicate with B.

A wiretapper C could steal the million puzzles. However, C would need to crack all million of the puzzles in order to discover the shared key. (If the wiretapper didn't know the pre-arranged string, then it can't even use a known-plaintext attack.) Since cracking each puzzle requires at least 2 minutes, the wiretapper would need on average 330 days to find the key.

2. RSA
The RSA cryptosystem is based on the assumption that factoring large integers is computationally hard. This assumption is not known to be true, but is widely believed. It is not even known if factoring is an NP-complete problem. RSA keys are often of length a power of two, like 512, 1024, or 2048 bits.

The RSA algorithm operates as follows

To setup a public-private key pair, principal A chooses two primes p and q and keeps them secret. A then computes n = p*q.
A chooses e relatively prime to (p-1)*(q-1) (e can be small; often 3, 17, or 65537 are chosen). It must be less than (p-1)(q-1).
public key is (e, n) and the private key is (d, n), where d is the multiplicative inverse of e mod(p-1)(q-1). A publishes (e, n) to complete the setup (usually with a Certificate Authority (CA)).

encryption of plaintext m: compute me mod n
decryption of ciphertext c: compute m = cd mod n
RSA works because c = me, so cd = md e mod n = m mod n (need to apply Fermat's Little Theorem and the Chinese Remainder Theorem)

RSA as described above suffers from several problems given our definitions. First, it is deterministic, since a given message always encrypts to the same ciphertext. Further, it does not satisfy Non-Malleability, since two encryptions, can, for example, be multiplied to get a new encryption: me * (m')e mod n = (m*m')e mod n. In some contexts, this kind of malleability can be useful, but it should be taken into account when designing systems that use RSA.

One simple way to solve malleability problems is to add some sort of Message Integrity Check (MIC) using hash functions. For instance, if instead of computing me mod n, we computed (m || h(m))e mod n for some h chosen from a family H of collision-resistant hash functions, then the product would be ((m || h(m)) * (m' || h(m')))e mod n, which is (m'' || h(m''))e mod n for some m'', but h being a one-way function guarantees that it is hard for the adversary to find an m'' for which this holds.

RSA signatures
As noted in the discussion on trapdoor functions, signatures can sometimes be constructed from encryption functions. RSA signatures function in a similar manner.

signing message m: s = md mod n.
checking message-signature pair (m, s): return true if m = se mod n
RSA signatures suffer from similar problems to malleability, but now these problems violate the fundamental CMA property of signature schemes. Since any two signatures can be combined to get a signature on a new message, it is trivial for an attacker in the CMA model to violate security.

The common solution to this problem is to hash the message first. Compute signature s = h(m)d mod n. Then even though the above attacks can be applied, the adversary can't figure out which message has been signed (to do so would require, given h(m)*h(m'), finding an m'' such that h(m'') = h(m)*h(m') mod n, which is prevented by pre-image resistance of the hash function).

3. ElGamal
ElGamal is an encryption scheme that, like RSA, depends on computational assumptions to guarantee security. Unlike the RSA assumption, however, ElGamal depends on an type of assumption called the discrete-logarithm assumption. Roughly, this assumption claims that it is hard in some groups to find x given gx mod n. The name comes from the fact that x log(g) mod n = log(gx) mod n and division is easy to compute in a group, so x is easy to compute given log(gx) mod n. ElGamal operates as follows.

generate safe prime p (this means that there exists a prime q such that p = 2q+1).
Let H be the field of integers mod p and G be the field of integers mod q. Choose g as a generator of G, which means that all elements of G are expressible as some power of g (it is easy to find such generators)
Choose a random x in G as a private key and compute y = gx mod p. Public key is (p, g, y).

encryption of plaintext m in G: encode m into M in H, choose random r in G, and output c = (gr, yr * M mod p)
decryption of ciphertext (a, b): output m = b / ax mod p
ElGamal works because ax = gr x and b = yr * M = gr x * M. Note that this uses probabilistic encryption, and has been proven secure in some models.

ElGamal as described here also suffers from malleability attacks. Of course, these "attacks" can be useful in some systems that require manipulation of encrypted values without revealing these values. There exist signature functions, called Schnorr signatures, that give non-malleable ElGamal construction.

4. Elliptic Curve Cryptography (ECC)
Most public-key cryptosystems are built over arithmetic in finite fields (algebraic structures that have addition and multiplication operations each with inverses). Elliptic Curve Cryptography (ECC) builds a finite field out of the set of solutions to an elliptic curve equation y2 = x3 + ax + b along with an additive identity element (that corresponds to the point at infinity).

We won't go into the details of constructing ECC versions of common cryptosystems, but several such examples exist. It should be noted that the addition operation in the group is not simply adding solutions in the underlying field.

ECC is valuable because it is believed to be harder to compute, e.g., discrete logs over the finite fields of ECC than in the underlying integer finite fields. This means that key sizes in ECC can be smaller than the corresponding key sizes in cryptosystems based on other fields. ECC is not, however, known to be harder than any other system.

Implementing Asymmetric Encryption

Public Function AEnc(ByVal strDataIn As String, ByVal CodeKey As String) As String
        Dim i As Integer
        Dim k As Integer
        Dim j As Long
        Dim StrOut As String
        StrOut = ""
        k = 1
        For j = 1 To Len(strDataIn)

            '>>> find the pkey value pair
            i = Asc(Mid(strDataIn, j, 1)) Xor Asc(Mid(CodeKey, k, 1)) '>>> written asc value
            '>>> convert into 3 digit
            Dim s1 As String
            If Len(CStr(i)) <= 1 Then
                s1 = "00" & i
            ElseIf Len(CStr(i)) <= 2 Then
                s1 = "0" & i
                s1 = i
            End If

            StrOut = StrOut & s1

            If k >= Len(CodeKey) Then
                k = 1
                k = k + 1
            End If
        AEnc = StrOut
End Function

For completing listing of the code and sample Visual Basic and C# .NET project for Asymmetric Encryption can be found in Sample Code section.

Home > Tips > Encryption and Decryption > Asymmetric Encryption