Definition

Contributor(s): Michael Cobb, Fred Hazan and Frank Rundatz

The RSA algorithm is the basis of a cryptosystem -- a suite of cryptographic algorithms that are used for specific security services or purposes -- which enables public key encryption and is widely used to secure sensitive data, particularly when it is being sent over an insecure network such as the internet.

RSA was first publicly described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology, though the 1973 creation of a public key algorithm by British mathematician Clifford Cocks was kept classified by the U.K.'s GCHQ until 1997.

Public key cryptography, also known as asymmetric cryptography, uses two different but mathematically linked keys -- one public and one private. The public key can be shared with everyone, whereas the private key must be kept secret.

In RSA cryptography, both the public and the private keys can encrypt a message; the opposite key from the one used to encrypt a message is used to decrypt it. This attribute is one reason why RSA has become the most widely used asymmetric algorithm: It provides a method to assure the confidentiality, integrity, authenticity, and non-repudiation of electronic communications and data storage.

Many protocols like secure shell, OpenPGP, S/MIME, and SSL/TLS rely on RSA for encryption and digital signature functions. It is also used in software programs -- browsers are an obvious example, as they need to establish a secure connection over an insecure network, like the internet, or validate a digital signature. RSA signature verification is one of the most commonly performed operations in network-connected systems.

### Why the RSA algorithm is used

RSA derives its security from the difficulty of factoring large integers that are the product of two large prime numbers. Multiplying these two numbers is easy, but determining the original prime numbers from the total -- or factoring -- is considered infeasible due to the time it would take using even today's supercomputers.

The public and private key generation algorithm is the most complex part of RSA cryptography. Two large prime numbers, p and q, are generated using the Rabin-Miller primality test algorithm. A modulus, n, is calculated by multiplying p and q. This number is used by both the public and private keys and provides the link between them. Its length, usually expressed in bits, is called the key length.

Alan Way explains how RSA public key
encryption works

The public key consists of the modulus n and a public exponent, e, which is normally set at 65537, as it's a prime number that is not too large. The e figure doesn't have to be a secretly selected prime number, as the public key is shared with everyone.

The private key consists of the modulus n and the private exponent d, which is calculated using the Extended Euclidean algorithm to find the multiplicative inverse with respect to the totient of n.

Read on or watch the video below for a more detailed explanation of how the RSA algorithm works.

### How does the RSA algorithm work?

Alice generates her RSA keys by selecting two primes: p=11 and q=13. The modulus is n=p×q=143. The totient is n ϕ(n)=(p−1)x(q−1)=120. She chooses 7 for her RSA public key e and calculates her RSA private key using the Extended Euclidean algorithm, which gives her 103.

Bob wants to send Alice an encrypted message, M, so he obtains her RSA public key (n, e) which, in this example, is (143, 7). His plaintext message is just the number 9 and is encrypted into ciphertext, C, as follows:

Me mod n = 97 mod 143 = 48 = C

When Alice receives Bob's message, she decrypts it by using her RSA private key (d, n) as follows:

Cd mod n = 48103 mod 143 = 9 = M

To use RSA keys to digitally sign a message, Alice would need to create a hash -- a message digest of her message to Bob -- encrypt the hash value with her RSA private key, and add the key to the message. Bob can then verify that the message has been sent by Alice and has not been altered by decrypting the hash value with her public key. If this value matches the hash of the original message, then only Alice could have sent it -- authentication and non-repudiation -- and the message is exactly as she wrote it -- integrity.

Alice could, of course, encrypt her message with Bob's RSA public key -- confidentiality -- before sending it to Bob. A digital certificate contains information that identifies the certificate's owner and also contains the owner's public key. Certificates are signed by the certificate authority that issues them, and they can simplify the process of obtaining public keys and verifying the owner.

### RSA security

RSA security relies on the computational difficulty of factoring large integers. As computing power increases and more efficient factoring algorithms are discovered, the ability to factor larger and larger numbers also increases.

Encryption strength is directly tied to key size, and doubling key length can deliver an exponential increase in strength, although it does impair performance. RSA keys are typically 1024- or 2048-bits long, but experts believe that 1024-bit keys are no longer fully secure against all attacks. This is why the government and some industries are moving to a minimum key length of 2048-bits.

Barring an unforeseen breakthrough in quantum computing, it will be many years before longer keys are required, but elliptic curve cryptography (ECC) is gaining favor with many security experts as an alternative to RSA to implement public key cryptography. It can create faster, smaller and more efficient cryptographic keys.

Modern hardware and software are ECC-ready, and its popularity is likely to grow, as it can deliver equivalent security with lower computing power and battery resource usage, making it more suitable for mobile apps than RSA. Finally, a team of researchers, which included Adi Shamir, a co-inventor of RSA, has successfully created a 4096-bit RSA key using acoustic cryptanalysis; however, any encryption algorithm is vulnerable to attack.

This was last updated in November 2018

#### Join the conversation

Send me notifications when other members comment.
Many thanks :)
Cancel
Given the various stories linking RSA Security to the NSA’s attempts to weaken encryption products and subvert cryptography standards, how much faith do you have in the RSA cryptosystem and today’s popular encryption algorithms?
Cancel
I tend not to believe much of what I see on the news and little of what I read unless I can personally verify it. We have no way of knowing if or how the NSA has compromised RSA and other algorithms. "Trust no one" is a good plan, but not very workable. Until I see a direct effect, I will continue to have faith in our algorithms.

Cancel
Thanks so much.
Cancel
il faut suivre une stratégie basé sur la sécurité .
Cancel
Very well explained. Feels like I know RSA much better now.
Cancel
I've found a way to factorise 2-primes factors without having to divide anything by any other thing. The ranking of p, one of those primes in a certain one-dimensional array is enough to find its identity. Once p has been found and being the product pxq of public knowledge, finding q is a real poc.

Cancel

## SearchCloudSecurity

• ### Choosing between proxy vs. API CASB deployment modes

Curious how to choose the right CASB deployment mode for your organization? Before you buy, compare how proxy vs. API CASB ...

• ### How to use the Mitre ATT&CK framework for cloud security

Learn how to use the Mitre ATT&CK security framework to keep your enterprise cloud environment -- whether AWS, GCP, Azure, Azure ...

• ### How to build a cloud security operations center

To better protect workloads and data in the cloud, security operations centers collaborate with various IT teams. Learn how to ...

## SearchNetworking

• ### Network pros share Cisco DevNet certification advice

Cisco DevNet certifications require a lot of time investment, but network pros who pursue the certifications say the gained ...

• ### Cloud automation use cases for managing and troubleshooting

Cloud automation use cases highlight the benefits these tools can provide to companies evaluating how best to manage and ...

• ### A look inside the official Cisco DEVASC 200-901 guidebook

In this book excerpt, readers can explore the Cisco DEVASC 200-901 official guide and get a flavor of one of Cisco's newest exams...

## SearchCIO

• ### 5 ways to keep developers happy so they deliver great CX

Companies need to work on ensuring their developers are satisfied with their jobs and how they're treated, otherwise it'll be ...

Companies must balance customer needs against potential risks during software development to ensure they aren't ignoring security...

• ### 5 digital transformation success factors for 2021

With the right planning, leadership and skills, companies can use digital transformation to drive improved revenues and customer ...

## SearchEnterpriseDesktop

• ### 11 tips to improve Windows 10 performance

With a few minor tweaks, such as maximizing RAM, disabling visual effects and getting rid of unnecessary services, you can ...

• ### Microsoft Pluton chip will secure future Windows PCs

Microsoft said its Pluton security chip would protect data even when an attacker has physical control of a computer. Future ...

• ### How does Microsoft 365 extend Windows 7 support?

Microsoft is ending its official support for Windows 7. However, Microsoft 365 customers have the option to extend support via ...

## SearchCloudComputing

• ### A conference guide to AWS re:Invent 2020

Stay on top of the latest news, analysis and expert advice from this year's re:Invent conference.

• ### Cognito user pools vs. identity pools -- what AWS users should know

Familiarize yourself with user pools and identity pools in Amazon Cognito and learn how to better protect your workloads in a ...

• ### How to containerize legacy applications in an Azure migration

There are many benefits to containerization as part of a migration, but only for the right type of app. If you're moving to Azure...

## ComputerWeekly.com

• ### This Christmas, Covid-19 heightens retail security risks for everyone

Do you think it’s only retailers and consumers who need to consider cyber security when shopping online during the holidays? You’...

• ### Broadband access drives New Zealand remote working to be permanent fixture

Covid-19 crisis pushes Kiwis to do more online and the changes are sticking, according to research from ANZ telco and media ...

• ### Government must hold technology companies to account on e-waste

MPs urge UK government and global technology companies to deal with ‘tsunami of electronic waste’, which is throwing away ...

Close