RSA (cryptosystem) facts for kids

RSA stands for Rivest–Shamir–Adleman. It is a very important way to send secret messages. This method is called a public-key cryptosystem. It is one of the oldest and most used systems for keeping data safe when it travels online.

The name "RSA" comes from the last names of the three people who first shared it with the public. They were Ron Rivest, Adi Shamir, and Leonard Adleman. They described their system in 1977. However, a similar system was secretly made in 1973 by a British mathematician named Clifford Cocks. His work was kept secret until 1997.

In a public-key system, there are two special keys. One key is public, meaning everyone can see it. This is the encryption key. The other key is secret, and only the owner knows it. This is the decryption key.

An RSA user makes a public key using two very large prime numbers. These prime numbers are kept secret. Anyone can use the public key to scramble a message. But only the person who knows the secret prime numbers can unscramble it.

The safety of RSA depends on how hard it is to break a big number into its prime parts. This is called the "factoring problem". If someone can break the number, they can break the code. There are no known ways to break RSA if the keys are large enough.

RSA is a bit slow for scrambling huge amounts of data directly. So, it is often used to send smaller, secret "keys" for other, faster scrambling methods. These faster methods then handle the main data.

History of RSA

Adi Shamir, one of the people who helped create RSA.

The idea of using two keys, one public and one private, came from Whitfield Diffie and Martin Hellman. They shared this idea in 1976. They also thought about digital signatures.

Ron Rivest, Adi Shamir, and Leonard Adleman worked at the Massachusetts Institute of Technology. They spent a year trying to create a special math function. This function would be easy to do one way but very hard to undo. Rivest and Shamir came up with many ideas. Adleman, a mathematician, would then try to find weaknesses in their ideas.

One night in April 1977, Rivest had an idea. He spent the rest of the night working on it. By morning, he had most of the plan ready. This plan became known as RSA, using the first letters of their last names.

A British mathematician named Clifford Cocks had already created a similar system in 1973. He worked for a secret intelligence agency called Government Communications Headquarters (GCHQ). At that time, computers were not powerful enough to use his system easily. So, it was mostly a curious idea. His discovery was kept top secret until 1997.

There is also a simpler version called Kid-RSA (KRSA). It was made in 1997 for teaching purposes. It helps people understand how RSA works.

RSA Patent Information

A patent for the RSA algorithm was given to MIT in 1983. It was called "Cryptographic communications system and method."

The details of the RSA algorithm were shared publicly in August 1977. This was in a magazine called Scientific American. This happened before the patent was even filed in December 1977. Because of this, the patent was not valid outside the United States. If Cocks's work had been known publicly, the patent would not have been valid in the U.S. either.

Patents used to last for 17 years. The RSA patent was going to end on September 21, 2000. But RSA Security decided to make the algorithm free for everyone on September 6, 2000.

How RSA Works

The RSA process has four main steps. These are making the keys, sharing the public key, scrambling a message, and unscrambling it.

The main idea behind RSA is that you can find three very large numbers. Let's call them e, d, and n. These numbers work together in a special way. If you have a message, m, you can scramble it using e and n. Then, you can unscramble it using d and n to get m back. It is very hard to find d if you only know e and n.

RSA uses a public key and a private key. The public key is known by everyone. It is used to scramble messages. Messages scrambled with the public key can only be unscrambled by someone with the private key. The public key is made of the numbers n and e. The private key is the number d. The message is represented by m.

Making the Keys

Here is how the keys for RSA are made:

• First, pick two very large prime numbers. Let's call them p and q.
  • To make it harder to break the code, p and q should be chosen randomly. They should be very large and different from each other.
  • Keep p and q a secret.
• Next, multiply p and q together to get n.
  • n is used for both the public and private keys. Its size, in bits, is the key length.
  • n is shared as part of the public key.
• Calculate a special number called λ(n). This number is found using p and q.
  • This λ(n) number must be kept secret.
• Choose a number e. This number must be between 2 and λ(n). Also, e and λ(n) must not share any common factors other than 1.
  • A common choice for e is 65,537. This helps make scrambling faster.
  • e is shared as part of the public key.
• Find a number d. This d is the special opposite of e when doing math with λ(n).
  • d can be found using a math method called the extended Euclidean algorithm.
  • d is kept secret. It is your private key.

The public key is made of n and e. The private key is d. The numbers p, q, and λ(n) must also be kept secret. Once d is found, these numbers can be thrown away.

Sharing the Key

Imagine Bob wants to send a secret message to Alice. If they use RSA, Bob needs Alice's public key to scramble the message. Alice then uses her private key to unscramble it.

Alice sends her public key (n, e) to Bob. She can send it over any channel, even if it's not secret. Alice's private key (d) is never shared with anyone.

Scrambling a Message (Encryption)

Once Bob has Alice's public key, he can send her a message.

• First, Bob turns his message into a number, m. He uses a special method called a padding scheme to prepare it. This m must be smaller than n.
• Then, Bob calculates the scrambled message, c. He uses Alice's public key e and the number n. The calculation is: c = m raised to the power of e, then divided by n with only the remainder kept.
• This calculation can be done quickly, even with very large numbers.
• Bob then sends c to Alice.

Unscrambling a Message (Decryption)

Alice can get the original message m back from c. She uses her private key d and the number n. The calculation is: m = c raised to the power of d, then divided by n with only the remainder kept.

Once Alice has m, she can turn it back into the original message by reversing the padding scheme.

Signing Messages

RSA can also be used to "sign" a message. This proves who sent it.

• Suppose Alice wants to send a signed message to Bob.
• She first creates a short "fingerprint" of her message. This is called a hash value.
• Then, she uses her own private key d to scramble this hash value. This scrambled hash is her "signature." She attaches it to the message.
• When Bob gets the message, he creates his own hash value of the message.
• He then uses Alice's public key e to unscramble her signature.
• If his hash value matches the unscrambled signature, he knows two things:
  • The message really came from Alice (because only she has her private key).
  • The message has not been changed since she sent it.

This works because the math allows the keys to be swapped. A private key can either unscramble a message meant only for the owner, or it can "scramble" a signature that anyone can check.

Security and Practical Points

The safety of RSA relies on how hard it is to break large numbers into their prime factors. If someone can factor the number n (which is p times q), they can find the private key.

Padding Schemes for Safety

Without special "padding," RSA can have weaknesses. For example, if you encrypt a very small message, it might be easy to guess. Also, if the same message is sent to many people, it could be easier to break.

To avoid these problems, real RSA systems add random "padding" to the message before scrambling it. This padding makes sure the message is always a good size. It also makes sure that the same message will look different each time it's scrambled.

Standards like PKCS#1 help design good padding. Newer versions of these standards use something called Optimal Asymmetric Encryption Padding (OAEP). This helps prevent certain attacks.

Key Generation Issues

It is very important to choose the large prime numbers p and q carefully.

• They should not be too close to each other.
• Their numbers minus one (p-1 and q-1) should not have only small prime factors.
• The private key d must be large enough. If it's too small, it can be guessed.

A common public key exponent e is 65,537. This number balances speed and safety.

Importance of Random Numbers

When making the keys, it's critical to use a very good random number generator. If the random numbers are not truly random, the keys can be weak.

In 2012, researchers found that about 0.2% of RSA keys on the internet were weak. This happened because some systems used bad random numbers. If two different public keys accidentally shared one of the same prime numbers (like p), then both keys could be broken easily. This problem often happened in small devices like firewalls and routers.

To fix this, systems need to use truly random "seeds" when generating keys. These seeds can come from things like keyboard presses or electronic noise.

Timing Attacks

In 1995, a new type of attack was found. If an attacker could measure how long it took a computer to unscramble messages, they might be able to figure out the private key.

To stop this, most RSA systems use a trick called cryptographic blinding. This makes the unscrambling time always the same, so attackers cannot learn anything from it.

Tricky to Implement Securely

Making RSA work safely is complex. You need good random numbers and proper padding. Because of these challenges, some experts suggest using other encryption methods if possible.

RSA Implementations

Many computer programs and libraries use RSA. Here are some of them:

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• Libgcrypt
• Nettle
• OpenSSL
• wolfCrypt
• GnuTLS
• mbed TLS
• LibreSSL

Images for kids

• 

  Adi Shamir, co-inventor of RSA (the others are Ron Rivest and Leonard Adleman)

See also

In Spanish: RSA para niños

• Acoustic cryptanalysis
• Computational complexity theory
• Diffie–Hellman key exchange
• Digital Signature Algorithm
• Elliptic-curve cryptography
• Key exchange
• Key management
• Key size
• Public-key cryptography
• Trapdoor function