codebreaking spy
counton.org
codebreaking logo

Developments in Cryptography, Public Key Systems

The RSA Algorithm

RSA cryptography is used to encrypt messages sent in the PGP email system, on the internet, when you use your mobile phone, and many other everyday events. The initials RSA stand for the inventors names – Ron Rivest, Adi Shamir and Len Adleman.

Key Generation

  1. Generate two large prime numbers, p and q
  2. Let n = pq
  3. Let m = (p-1)(q-1)
  4. Choose a small number e , coprime to m
  5. Find d , such that de % m = 1

Publish e and n as the public key.
Keep d and n as the secret key.

Encryption

C = P e % n

Decryption

P = C d % n

x % y means the remainder of x divided by y

THIS TABLE HAS BEEN COPIED FROM http://pajhome.org.uk/crypt/rsa/rsa.html

THERE IS MORE INFO ON THIS PAGE AND ALSO http://pajhome.org.uk/crypt/rsa/maths.html

HERE IS ANOTHER SITE ON THE MATHS BEHIND RSA http://en.wikipedia.org/wiki/RSA

Much like the OTP the strength of the RSA Algorithm is based on the difficulty in factoring large numbers. RSA is often used to encrypt the key for a symmetrical cipher

RSA is only used to encrypt numbers and is well suited to the binary language used by computers. However, because plaintext is often predictable – for example, if you know a message you have intercepted says either ‘we will attack by air' or \‘we will attack by sea', you can encipher both messages using the public key and compare the results to the intercepted cipher. One way of decreasing this risk is to incorporate chunks of random \‘junk' code into messages.

The encryption and decryption techniques for the RSA cipher are so similar that it is possible to swap them and encrypt a message using the private key. This produces a digital signature which can then be decoded by the public key, and easily identifies the sender.


PGP

PGP (Pretty Good Privacy) is a public key system that uses the RSA algorithm to encrypt electronic mail. It is a hybrid of four different cryptographic elements – a symmetrical cipher (IDEA), an asymmetrical cipher (RSA), a one-way hash (MD5), and a random number generator (PRNG).

When you send a message, PGP encrypts the message using a randomly generated session key that is used only for that message. It then encrypts the key using the public RSA key. When the recipient receives the encrypted message and key PGP then decrypts the sender’s key using his or her private key and uses that to decrypt the message.


One-Way Functions

Although you’re probably not aware of it, we use One-Way Functions all the time. They are used to encrypt electronic information, such as your credit card data when you purchase something online.

One-way functions are public key cryptosystems. The public key gives information as to the forward function – encoding, but you would need the private key in order to be able to decrypt the information. So, if you purchased an item online with a credit card, your information would be encrypted using the public key, but would only be accessible to the seller who knows the private key.’

They are very secure as they work on the basis that prime factorisation is extremely completed and virtually impossible. It is extremely different to factor a large number into its prime factors, but not to multiply them in the first place. Hence the ‘one-way’ nature of the function.