- CS Project
- MBA Project
- Certification
- Interview
- Download
- Tips
- Forum
- Encryption & Decryption
- Encryption & Decryption
- XOR Encryption
- Transposition Encryption
- Symmetric Encryption
- Asymmetric Encryption
- Certificate Authority
- Decryption Logics
- Sample Coding

- Encryption & Decryption
- Encryption & Decryption
- XOR Encryption
- Transposition Encryption
- Symmetric Encryption
- Asymmetric Encryption
- Certificate Authority
- Decryption Logics
- Sample Coding

Home > Tips > Encryption and Decryption > Asymmetric Encryption

**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.

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.

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

Setup:

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)).

Operations:

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.

Setup:

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).

Operations:

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

Else

s1 = i

End
If

StrOut = StrOut & s1

If k >=
Len(CodeKey) Then

k = 1

Else

k = k + 1

End
If

Next

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

© 2006 - 2024, RM Solution.