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