Scribd
Upload
5 views3 pages

Cryptography

RSA is an asymmetric cryptographic algorithm that uses a key pair for secure data transmission, relying on the difficulty of factoring large prime numbers. The key generation process involves selecting primes, computing modulus and totient, and determining public and private exponents. RSA is also used for digital signatures and faces vulnerabilities such as small prime attacks and side-channel attacks, but remains essential for secure internet communication despite potential threats from quantum computing.

Uploaded by

ebn9z8kaw
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views3 pages

Cryptography

RSA is an asymmetric cryptographic algorithm that uses a key pair for secure data transmission, relying on the difficulty of factoring large prime numbers. The key generation process involves selecting primes, computing modulus and totient, and determining public and private exponents. RSA is also used for digital signatures and faces vulnerabilities such as small prime attacks and side-channel attacks, but remains essential for secure internet communication despite potential threats from quantum computing.

Uploaded by

ebn9z8kaw
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Cryptography & Network Security

Title: The Mathematical Foundations of RSA and Public Key


Infrastructure (PKI)
1. Overview
RSA (Rivest–Shamir–Adleman) is an asymmetric cryptographic
algorithm widely used for secure data transmission. Unlike
symmetric algorithms (like AES) which use a single key, RSA
utilizes a key pair: a Public Key for encryption and a Private Key
for decryption. The security of RSA relies on the practical
difficulty of factoring the product of two large prime numbers,
the "factoring problem."
2. Key Generation Algorithm
The generation of an RSA key pair involves the following steps:
1. Select Primes: Choose two distinct large prime numbers,
$p$ and $q$.
2. Compute Modulus: Calculate $n = p \times q$. The value
$n$ is used as the modulus for both the public and private
keys. The length of $n$ in bits (e.g., 2048) is the key length.
3. Compute Totient: Calculate Euler's totient function
$\phi(n)$:
$$\phi(n) = (p-1)(q-1)$$
4. Choose Public Exponent: Select an integer $e$ such that $1
< e < \phi(n)$ and $gcd(e, \phi(n)) = 1$. A common choice for
$e$ is $65537$ ($2^{16} + 1$) because it is a prime number
that allows for efficient encryption.
5. Compute Private Exponent: Determine $d$ as the modular
multiplicative inverse of $e$ modulo $\phi(n)$. This means:
$$d \cdot e \equiv 1 \pmod{\phi(n)}$$
This is typically computed using the Extended Euclidean
Algorithm.
3. Encryption and Decryption Primitives
• Public Key: $(n, e)$
• Private Key: $(d)$
Given a plaintext message $M$ (represented as an integer where
$0 \le M < n$):
• Encryption: The ciphertext $C$ is computed as:
$$C \equiv M^e \pmod n$$
• Decryption: The original message $M$ is recovered using
the private key:
$$M \equiv C^d \pmod n$$
• Proof of Correctness:
$$C^d \equiv (M^e)^d \equiv M^{ed} \pmod n$$
Since $ed \equiv 1 \pmod{\phi(n)}$, Euler's Theorem guarantees
that $M^{ed} \equiv M \pmod n$.
4. Digital Signatures
RSA is also used for authentication. To sign a message, the
sender encrypts the hash of the message with their Private Key.
$$S \equiv H(M)^d \pmod n$$
The receiver verifies the signature by decrypting it with the
sender's Public Key and comparing it to the hash of the received
message. If they match, the message is authentic and has not
been tampered with.
5. Security Vulnerabilities
• Small Prime Attacks: If $p$ or $q$ are too small, $n$ can be
factored easily.
• Side-Channel Attacks: Attackers monitor power
consumption or timing during the decryption process to
infer bits of the private key $d$.
• Padding Oracle Attacks: Without proper padding (like
OAEP), RSA is deterministic and vulnerable to chosen-
ciphertext attacks.
6. Conclusion
While Quantum Computing poses a theoretical threat to RSA (via
Shor's Algorithm), it remains the bedrock of secure internet
communication (HTTPS/TLS) today. Implementing RSA requires
careful attention to random number generation and padding
schemes to maintain security.

You might also like