91Ó°ÊÓ

Modular arithmetic is a fundamental concept in number theory and cryptography.
It involves numbers wrapping around after reaching a certain value, known as the modulus. For instance, in a 12-hour clock, if you add 1 hour to 12, it wraps around to 1 instead of 13. This is described by the equation:
\[ a \bmod n = r \]
Where \( a \) is the dividend, \( n \) is the divisor, and \( r \) is the remainder when \( a \) is divided by \( n \).
The use of modular arithmetic in RSA encryption ensures that calculations remain within a feasible range and avoid overflow.
When encrypting or decrypting messages, modular arithmetic helps in transforming values without going out of bounds, making it both efficient and secure.

Public key cryptography uses pairs of keys: one public and one private.
The public key is shared openly, while the private key remains confidential. RSA (Rivest-Shamir-Adleman) is a widely-used public key cryptosystem.

RSA encryption involves a few critical steps:
* Key Generation: Large prime numbers \( p \) and \( q \) are selected.
* Public Key Formation: Compute \( n = p \times q \) and select a public exponent \( e \) such as 3.
* Private Key Formation: Generate the private decryption key \( d \) such that it satisfies \( e \times d \bmod \phi(n) = 1 \), where \( \phi(n) = (p-1) \times (q-1) \).

Encryption and decryption processes rely on these key pairs.
* Encryption: \( c = m^e \bmod n \) where \( m \) is the message, \( e \) is the public key exponent, and \( n \) is the modulus.
* Decryption: \( m = c^d \bmod n \)
Using public key cryptography, even if someone knows \( e \) and \( n \), they cannot easily deduce \( d \), ensuring message security.

Modular exponentiation is a technique used to efficiently compute large powers in modular arithmetic.
Given values \( a \), \( b \), and \( n \), modular exponentiation finds \( a^b \bmod n \).
This is crucial for avoiding overflow and speeding up calculations.

The method involves breaking down \( b \) into its binary form and using the properties of exponents to reduce the number of multiplications.
For example, to compute \( a^b \bmod n \):
1. Start with the base result set to 1.
2. Repeatedly square the base and multiply by \( a \) when required, always taking modulus \( n \).

The steps for our example are:
- Compute \( c = 9876^3 \bmod 11413 \)
- Decompose the exponent: \( 3 = 2^1 + 2^0 \)
- Compute: \( 9876^1 \bmod 11413, 9876^2 \bmod 11413, \text{ then add the results} \)
Efficient calculation reduces computational complexity, crucial for large numbers in RSA encryption.

Euler's Totient Function \( \phi(n) \) is a key concept in number theory and cryptography.
For a number \( n \), it counts integers up to \( n \) that are coprime with \( n \), meaning their greatest common divisor with \( n \) is 1.

For RSA, where \( n = p \times q \) with prime \( p \) and \( q \), Euler's Totient Function \( \phi(n) \) is calculated as:
\[ \phi(n) = (p-1) \times (q-1) \]
This establishes the number of integers less than \( n \) that have no common factors with \( n \).

The totient function impacts the formation of private and public keys.
Specifically, it ensures the existence of a multiplicative inverse, meaning for a given \( e \), there exists a unique \( d \) such that:
\[ e \times d \bmod \phi(n) = 1 \]
Calculating \( \phi(n) \) is straightforward for RSA since \( p \) and \( q \) are prime.
In our example with \( p = 101 \) and \( q = 113 \), Euler's Totient Function yields:
\[ \phi(n) = (101-1) \times (113-1) = 11200 \]
This value plays a crucial role in the decryption process.