Protocol++® (Protocolpp®)  v5.6.2
jrsa Class Reference

#include "include/jrsa.h"

Detailed Description

RSA CyptoSystem

see https://en.wikipedia.org/wiki/RSA_(cryptosystem)

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the "factoring problem". The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), had developed an equivalent system in 1973, but this was not declassified until 1997

A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, and if the public key is large enough, only someone with knowledge of the prime numbers can decode the message feasibly.[2] Breaking RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem remains an open question. RSA is a relatively slow algorithm, and because of this, it is less commonly used to directly encrypt user data. More often, RSA passes encrypted shared keys for symmetric key cryptography which in turn can perform bulk encryption-decryption operations at much higher speed

The idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published this concept in 1976. They also introduced digital signatures and attempted to apply number theory. Their formulation used a shared-secret-key created from exponentiation of some number, modulo a prime number. However, they left open the problem of realizing a one-way function, possibly because the difficulty of factoring was not well-studied at the time

Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology made several attempts, over the course of a year, to create a one-way function that was hard to invert. Rivest and Shamir, as computer scientists, proposed many potential functions, while Adleman, as a mathematician, was responsible for finding their weaknesses. They tried many approaches including "knapsack-based" and "permutation polynomials". For a time, they thought what they wanted to achieve was impossible due to contradictory requirements.[4] In April 1977, they spent Passover at the house of a student and drank a good deal of Manischewitz wine before returning to their homes at around midnight. Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function. He spent the rest of the night formalizing his idea, and he had much of the paper ready by daybreak. The algorithm is now known as RSA – the initials of their surnames in same order as their paper

Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described an equivalent system in an internal document in 1973. However, given the relatively expensive computers needed to implement it at the time, RSA was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification.

Operation

The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption

A basic principle behind RSA is the observation that it is practical to find three very large positive integers $ e$, $ d$ and $ n$ such that with modular exponentiation for all integers $ m$ (with $ 0 \leq m < n$):

$ {({m}^{e})}^{d} \equiv m (mod n)$

and that even knowing $ e$ and $ n$ or even $ m$ it can be extremely difficult to find $ d$

In addition, for some operations it is convenient that the order of the two exponentiations can be changed and that this relation also implies:

$ {({m}^{d})}^{e} \equiv m ( mod n )$

RSA involves a public key and a private key. The public key can be known by everyone, and it is used for encrypting messages. The intention is that messages encrypted with the public key can only be decrypted in a reasonable amount of time by using the private key. The public key is represented by the integers $ n$ and $ e$; and, the private key, by the integer $ d$ (although $ n$ is also used during the decryption process. Thus, it might be considered to be a part of the private key, too). $ m$ represents the message (previously prepared with a certain technique explained below)

Key generation

The keys for the RSA algorithm are generated the following way:

  • Choose two distinct prime numbers p and q
    • For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but differ in length by a few digits to make factoring harder Prime integers can be efficiently found using a primality test
  • Compute $ n = pq$
    • n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length
  • Compute $ \lambda(n) = lcm(\lambda(p), \lambda(q)) = lcm(p−1, q−1)$, where $ \lambda$ is Carmichael's totient function. This value is kept private
  • Choose an integer $ e$ such that $ 1 < e < \lambda(n)$ and $ gcd(e, \lambda(n)) = 1$; i.e., $ e$ and $ \lambda(n)$ are coprime
  • Determine $ d$ as $ d \equiv {e}^{−1} (mod \lambda(n))$; i.e., $ d$ is the modular multiplicative inverse of $ e mod \lambda(n)$
    • This means: solve for $ d$ the equation $ d \cdot e \equiv 1 (mod \lambda(n))$
    • $ e$ having a short bit-length and small Hamming weight results in more efficient encryption – most commonly $ e = {2}^{16} + 1 = 65,537$. However, much smaller values of $ e$ (such as 3) have been shown to be less secure in some settings
    • $ e$ is released as the public key exponent
    • $ d$ is kept as the private key exponent

The public key consists of the modulus $ n$ and the public (or encryption) exponent $ e$. The private key consists of the private (or decryption) exponent $ d$, which must be kept secret. $ p, q$, and $ \lambda(n)$ must also be kept secret because they can be used to calculate $ d$

In the original RSA paper, the Euler totient function $ \phi(n) = (p − 1)(q − 1)$ is used instead of $ \lambda(n)$ for calculating the private exponent $ d$. Since $ \phi(n)$ is always divisible by $ \lambda(n)$ the algorithm works as well

Key distribution

Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice's public key to encrypt the message and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key $ (n, e)$ to Bob via a reliable, but not necessarily secret, route. Alice's private key ( $ d$) is never distributed

Encryption

After Bob obtains Alice's public key, he can send a message $ M$ to Alice. To do it, he first turns $ M$ (strictly speaking, the un-padded plaintext) into an integer $ m$ (strictly speaking, the padded plaintext), such that $ 0 ≤ m < n$ by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext $ c$, using Alice's public key $ e$, corresponding to $ c \equiv {m}^{e} (mod n)$

This can be done reasonably quickly, even for 500-bit numbers, using modular exponentiation. Bob then transmits $ c$ to Alice

Decryption

Alice can recover $ m$ from $ c$ by using her private key exponent $ d$ by computing

$ {c}^{d} \equiv {({m}^{e})}^{d} \equiv m (mod n)$

Given $ m$, she can recover the original message $ M$ by reversing the padding scheme

Signing messages

Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she can claim to be Alice but Bob has no way of verifying that the message was actually from Alice since anyone can use Bob's public key to send him encrypted messages. In order to verify the origin of a message, RSA can also be used to sign a message

Suppose Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a hash value of the message, raises it to the power of $ d (mod n)$ (as she does when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he uses the same hash algorithm in conjunction with Alice's public key. He raises the signature to the power of $ e (mod n)$ (as he does when encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's private key, and that the message has not been tampered with since

Padding schemes

To avoid these problems, practical RSA implementations typically embed some form of structured, randomized padding into the value m before encrypting it. This padding ensures that m does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts

Standards such as PKCS#1 have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintext m with some number of additional bits, the size of the un-padded message $ M$ must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks which may be facilitated by a predictable message structure. Early versions of the PKCS#1 standard (up to version 1.5) used a construction that appears to make RSA semantically secure

Secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption

Security

The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme

Importance of strong random number generation

A cryptographically strong random number generator, which has been properly seeded with adequate entropy, must be used to generate the primes $ p$ and $ q$

Strong random number generation is important throughout every phase of public key cryptography. For instance, if a weak generator is used for the symmetric keys that are being distributed by RSA, then an eavesdropper could bypass RSA and guess the symmetric keys directly

For API information:

See also
ProtocolPP::jrsa
ProtocolPP::jrand
ProtocolPP::jenum

For Additional Documentation:

See also
jrsa
jrand
jenum
Protocol++® (ProtocolPP®) written by : John Peter Greninger • © John Peter Greninger 2015-2024 • All Rights Reserved
All copyrights and trademarks are the property of their respective owners

The source code contained or described herein and all documents related to the source code (herein called "Material") are owned by John Peter Greninger and Sheila Rocha Greninger. Title to the Material remains with John Peter Greninger and Sheila Rocha Greninger. The Material contains trade secrets and proprietary and confidential information of John Peter Greninger and Sheila Rocha Greninger. The Material is protected by worldwide copyright and trade secret laws and treaty provisions. No part of the Material may be used, copied, reproduced, modified, published, uploaded, posted, transmitted, distributed, or disclosed in any way without prior express written consent of John Peter Greninger and Sheila Rocha Greninger (both are required)

No license under any patent, copyright, trade secret, or other intellectual property right is granted to or conferred upon you by disclosure or delivery of the Materials, either expressly, by implication, inducement, estoppel, or otherwise. Any license under such intellectual property rights must be express and approved by John Peter Greninger and Sheila Rocha Greninger in writing

Licensing information can be found at www.protocolpp.com/license with use of the binary forms permitted provided that the following conditions are met:

  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution
  • Any and all modifications must be returned to John Peter Greninger at GitHub.com https://github.com/jpgreninger/protocolpp for evaluation. Inclusion of modifications in the source code shall be determined solely by John Peter Greninger. Failure to provide modifications shall render this license NULL and VOID and revoke any rights to use of Protocol++®
  • Commercial use (incidental or not) requires a fee-based license obtainable at www.protocolpp.com/shop
  • Academic or research use requires prior written and notarized permission from John Peter and Sheila Rocha Greninger

Use of the source code requires purchase of the source code. Source code can be purchased at www.protocolpp.com/shop

  • US Copyrights at https://www.copyright.gov/
    • TXu002059872 (Version 1.0.0)
    • TXu002066632 (Version 1.2.7)
    • TXu002082674 (Version 1.4.0)
    • TXu002097880 (Version 2.0.0)
    • TXu002169236 (Version 3.0.1)
    • TXu002182417 (Version 4.0.0)
    • TXu002219402 (Version 5.0.0)
    • TXu002272076 (Version 5.2.1)
    • TXu002383571 (Version 5.4.3)

The name of its contributor may not be used to endorse or promote products derived from this software without specific prior written permission and licensing

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE

The documentation for this class was generated from the following file: