Definition

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

RSA is a cryptosystem for public-key encryption, and is widely used for securing sensitive data, particularly when being sent over an insecure network such as the Internet.

RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. 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 of assuring the confidentiality, integrity, authenticity and non-reputability of electronic communications and data storage.

Many protocols like SSH, 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, which 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 IT.

### Explaining RSA's popularity

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 -- factoring -- is considered infeasible due to the time it would take even using today’s super computers.

The public and the 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. 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.

### A simple, worked example

Alice generates her RSA keys by selecting two primes: p=11 and q=13. The modulus n=p×q=143. The totient of 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 create a hash or message digest of her message to Bob, encrypt the hash value with her RSA private key and add it 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 can simplify the process of obtaining public keys and verifying the owner.

### Security of RSA

As discussed, the security of RSA 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 delivers 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 could be broken in the near future, which is why government and industry are moving to a minimum key length of 2048-bits. Barring an unforeseen breakthrough in quantum computing, it should be many years before longer keys are required, but elliptic curve cryptography is gaining favor with many security experts as an alternative to RSA for implementing public-key cryptography. It can create faster, smaller and more efficient cryptographic keys. Much of today’s hardware and software is 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 determined a 4096-bit RSA key using acoustic cryptanalysis, however any encryption algorithm is vulnerable to this type of attack.

The inventors of the RSA algorithm founded RSA Data Security in 1983. The company was later acquired by Security Dynamics, which was in turn purchased by EMC Corporation in 2006. The RSA algorithm was released to the public domain by RSA Security in 2000.

This was last updated in November 2014

## Content

Find more PRO+ content and other member only offers, here.

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

## SearchCloudSecurity

• ### How to prepare for a cloud DDoS attack on an enterprise

Suffering a cloud DDoS attack is now more likely than ever. Expert Frank Siemons discusses what enterprises need to know about ...

• ### Ownership of cloud risks gets lost in many cloud computing scenarios

CISOs ensure that cloud services comply with IT security and risk management policies. But who has executive oversight of ...

• ### Cloud incident response: What enterprises need to include in a plan

A cloud incident response plan can be difficult to assemble. Expert Rob Shapland discusses the basics of what to include in a ...

## SearchNetworking

• ### Delivering private and public cloud applications securely

'It's all about the apps' is today's mantra, and managing private and public cloud app delivery must be a top concern in order to...

• ### Gigabit Ethernet speeds: What's the impact of 2.5 and 5 GbE?

Gigabit Ethernet speeds mean enterprises can boost wireless performance without actually replacing wiring. But there are still ...

• ### Zero downtime goal of new industry group

Networking analysts discuss if a new zero-downtime initiative will be viable and the best way to unlock the value of the hybrid ...

## SearchCIO

• ### Renew vs. replace software? CFOs say it depends on business capabilities

CFOs discussed how they decide whether to keep or replace software at the recent MIT Sloan CFO Summit. Cloud looms large in their...

• ### Record-busting online holiday sales and the rise of the omnishopper

Record online holiday sales foretell the arrival of conversational commerce, digital humanism and the omnishopper. Also: AWS goes...

• ### Will AR and VR tech revolutionize digital business management?

In this issue of CIO Decisions, we explore how virtual reality and augmented reality technologies could quickly become integral ...

## SearchConsumerization

• ### Android, Windows tablets from HP take aim at business users

HP released a new line of tablets targeting business users. The HP Pro Slate 8 and Pro Slate 12 run Android and cost \$449 and ...

• ### Microsoft to lay off 18,000, Nokia X moves to Windows Phone

Microsoft will lay off 18,000 people over the next year while the Nokia X line of Android smartphones, which was unveiled earlier...

• ### Microsoft Surface Pro 3 vs. Microsoft Surface Pro 2

Surface Pro 2 and Surface Pro 3 are different enough that Microsoft is keeping both on the market as competing products. Which ...

## SearchEnterpriseDesktop

• ### VMware Identity Manager helps IT provide user access across device types

With Identity Manager, VMware's identity as a service offering, IT admins can deliver a variety of application types across ...

• ### Experts predict the future of Windows 10 and the Creators Update

Three experts share their thoughts on what's next for enterprise desktop admins in 2017, including what to expect from Windows 10...

If admins notice any issues with tasks running on Windows, they can turn to NirSoft's TaskSchedulerView to pinpoint the culprit ...

## SearchCloudComputing

• ### Ten ways to improve your private cloud self-service portal

A private cloud portal allows users to tap into the self-service benefits of cloud. Follow these ten steps to guarantee user ...

• ### Cloud computing programming API tutorial

Developers have a wide range of platforms to choose from to create cloud-based applications. Dive into cloud programming ...

• ### The hybrid cloud management platform and the modern enterprise

Hybrid cloud management is a hot issue for modern IT operations. Read more to find out what it is, how it works and what it can ...

## ComputerWeekly

• ### Government Transformation Strategy to 'fundamentally' change the way departments operate

A background document seen by Computer Weekly outlines details of the forthcoming Government Transformation Strategy

• ### IT Priorities 2017: Nordic organisations to spend more on cloud services

The adoption of cloud computing in its many guises will be a top priority in the Nordic region in 2017

• ### Blackberry changes tack to secure enterprise internet of things

After dropping devices to concentrate on mobile device management, Blackberry is poised to take on IoT security under John Chen’s...

Close