Message in a Bottle
Elliptic Curve PGP for SMS

• Presentation
• Tutorial
  • Basic Notions
  • Elliptic curve cryptography
  • Installation
  • Main Menu
  • Send public key
  • Receive public key
  • Send encrypted SMS
  • Program Registration
• Technical Details
• FAQ
• Forum
• Download
• Buy now

Elliptic Curve Cryptography

Message in a Bottle uses a public key cryptographic engine based on Elliptic Curve Cryptography (ECC).
Here we try to give a brief overview of Elliptic Curve Cryptography.  

Elliptic Curve Cryptography is a public key cryptographic system, invented separately by Neal Kiblitz e Victor Miller in 1985, based on Elliptic Curve theory defined on finite fields.

An elliptic curve

An elliptic curve is a plain curve defined by an equation like this:

y2 =  x3 + a x + b.

Solutions to such an equation, together with the point at infinity, form an abelian group (if we consider the point at infinity as identity element). If we take x and y from a finite field (i.e. considering only a finite number of points) the set composed by all solutions forms a finite abelian group.

Discrete Logarithm

The security of Elliptic Curve Cryptography is based upon discrete logarithm problem.
Discrete logarithm is defined as the logarithm, in base n, on an algebraic group (differently from canonical logarithm defined on the set of real numbers).
For example, consider the multiplicative group formed by integers modulo p:

G = Z*p    with p is a prime number (i.e. the set of integers {1,2....p})

Consider then the equation:

ax =  b mod p     (mod stays for  the rest of the division b/p)

discrete logarithm problem consists in finding a value for x such that the above equation is satisfied.

As of this writing there isn't any efficient algorithm to calculate discrete logarithms. It is a problem belonging to the NP (non-polinomial) class for which finding a solution requires an exponential time respect to dimensions of the algebraic group G.
It is exactly this feature that makes discrete logarithm problem the basis for public key cryptosystems.

Discrete logarithm problem is used for implementing the Diffie-Hellmann key agreement algorithm.

Diffie-Hellmann key agreement

Alice and Bob want to exchange encrypted messages. First of all, they must agree on a secret key used for encripting messages. So the problem is: How can they agree on a key securely? Diffie-Hellmann key agreement algorithm allows solving this problem:

1) Alice and Bob choose a specific elliptic curve  y2 =  x3 + a x + b setting values to a e b

2) Alice and Bob choo se on such a curve a point G (x, y) called generator.

3) Alice chooses an integer m large enough (private key) and calculates the value mG (public key) which she sends to Bob.

4) Bob chooses an integer n large enough (private key) and calculates the value nG (public key) which he sends to Alice

5) Both Alice and Bob have the value mnG which represents the needed key.

It Is proved that the problem of finding mnG knowing only mG or nG (Diffie-Hellmann problem for elliptic curve cryptography) is analogous to discrete logarithm problem (for a detailed proof see N. Koblitz, "Elliptic curve cryptosystems", in Mathematics of Computation 48, 1987, pp. 203–209).

Elliptic Curve Cryptography Strength

Discrete logarithm problem used in elliptic curve cryptography, considering the same finite field dimension, is considered more complex than integer factorization problem used by RSA cryptosystem. Thus, given a definite security level, elliptic curve cryptosystem requires keys smaller than the keys used by RSA cryptosystem.

As of this writing (2007), it doesn't exist any work which establish formerly and definetely the complexity level of elliptic curve cryptosystem.
Nevertheless National Security Agency acquired a new technology based on elliptic curve which has been inserted into the list of reccomended algorithm for "NSA Suite B".

Easier calculations

Another aspect which distinguish elliptic curve cryptosystem from RSA cryptosystem is the easier calculations required for producing the cryptographic quantities.
The most of calculations are additions and multiplications on integers and/or points on the curve. Viceversa, RSA cryptosystem requires modulus calculations considerably more complex and more hard in terms of calculation resources. Therefore elliptic curve cryptosystem better fits for implementations on devices with reduced resources such as smart cards, mobile phones and so on.

Elliptic Curve and  SMS

Elliptic curve cryptosystem has several nice features for SMS protection. First of allI, as already mentioned above, considering the same level of security, requires keys much smaller than RSA cryptosystem. Reffering to the picture above, a 160 bit elliptic key offers the same security level as a 1024 bit RSA key. Therefore, encrypted/signed SMSs are smaller than the length they  will have if using another cryptosystem.
Second, as already mentioned above, mathematic calculations required by elliptic curve cryptosystem are easier and, hence, they require a low calculation power. Therefore elliptic curve cryptography is the more appropriate cryptographic technology to be used on small devices such as mobile phones.