Podcast
Questions and Answers
What is the primary characteristic of private-key cryptography?
What is the primary characteristic of private-key cryptography?
What does the term 'asymmetric' refer to in public-key cryptography?
What does the term 'asymmetric' refer to in public-key cryptography?
Which of the following accurately describes the RSA encryption algorithm?
Which of the following accurately describes the RSA encryption algorithm?
What is a characteristic of public-key algorithms?
What is a characteristic of public-key algorithms?
Signup and view all the answers
Why is it critical to keep the private key secret in public-key cryptography?
Why is it critical to keep the private key secret in public-key cryptography?
Signup and view all the answers
What happens if the private key of a public-key cryptosystem is compromised?
What happens if the private key of a public-key cryptosystem is compromised?
Signup and view all the answers
What is a necessary property of the keys used in public-key cryptography?
What is a necessary property of the keys used in public-key cryptography?
Signup and view all the answers
Which statement best describes the relationship between the public key and the private key in a public-key cryptosystem?
Which statement best describes the relationship between the public key and the private key in a public-key cryptosystem?
Signup and view all the answers
Signup and view all the answers
Study Notes
Private-Key Cryptography
- Traditional private/secret/single-key cryptography employs one key shared by both sender and receiver
- If the key is disclosed, communications are compromised
- Symmetric; parties are equal
- Does not protect sender from receiver forging a message & claiming it was sent by sender
Public-Key Cryptography
- A significant advance in cryptography's 3000-year history
- Employs two keys: public & private
- Asymmetric; parties are unequal
- Uses number theory to function
- Complements (rather than replaces) private-key cryptography
Public-Key Cryptography (Details)
- Public-key/two-key/asymmetric cryptography uses two keys:
- A public key, accessible to anyone, used to encrypt messages and verify signatures.
- A private key, known only to the recipient, used to decrypt messages and sign (create) signatures.
- Asymmetric because those who encrypt or verify cannot decrypt or create signatures.
RSA Encryption Algorithm
- A type of public-key encryption algorithm.
- Asymmetric algorithm
- Sender and receiver use different keys for encryption and decryption.
- Each sender is assigned a pair of keys:
- Public key for encryption
- Private key for decryption
RSA Encryption Algorithm (Details)
- The public key is used for encryption, and the private key is used for decryption.
- Decryption cannot be performed using a public key.
- The two keys are linked, but the private key cannot be derived from the public key.
- The public key is publicly known.
- The private key is secret, known only to its owner
- Anyone can send a message using the public key
- Only the owner of the private key can decrypt the message.
RSA Encryption Algorithm (Procedure)
- Data to be sent is encrypted by sender A using the public key of recipient B
- B decrypts the ciphertext using its private key, known only to B
- B replies to A by encrypting its message to A using A's public key
- A decrypts using its private key, known only to A
RSA Encryption Algorithm (Procedure - Math)
- RSA employs modular arithmetic
- Encryption: C = Me mod n , where M is the plaintext, C is the ciphertext, e is the encryption exponent, and n is the modulus
- Decryption: M= Cd mod n, where d is the decryption exponent and all other variables are the same
RSA Algorithm (Key Generation)
- Select two large prime numbers, p and q
- Compute n = p x q, where n is the modulus used for encryption and decryption
- Calculate ø(n) =(p-1)x(q-1)
- Choose an encryption exponent, e, such that 1 < e < ø(n), and gcd(e, ø(n)) = 1
- Calculate the decryption exponent, d, such that (e x d) mod ø(n) = 1 (or eD mod φ (n) = 1)
- Publish the public key {e, n}
- Keep the private key {d, n} secret
RSA Algorithm (Example)
- Step 1: Select two large prime numbers, p=7, q=11
- Step 2: Compute n = p x q = 77
- Step 3: Compute ø(n) = (p - 1) x (q - 1) = 60
- Step 4: Choose e=7.
- Step 5: Calculate d, such that 7d mod 60 = 1; d=43 (in this example)
- Step 6: Public key is {7, 77}
- Step 7: Private key is {43, 77}
RSA Algorithm (En/Decryption)
- Encryption : Ciphertext C = M7 mod 77, where M is the plaintext message
- Decryption : Plaintext M = C43 mod 77 , where C is the ciphertext
Exponentiation
- Use the Square and Multiply Algorithm for fast exponentiation.
- This algorithm repeatedly squares the base and multiplies in ones needed to calculate the result.
- By looking at the binary representation of the exponent, only O(log n) multiples are needed for a number n.
Efficient Encryption
- Exponentiation (with exponent e) used in RSA encryption .
- Small e values lead to faster encryption.
- 65537 (216 - 1) or even smaller values are commonly selected.
- Proper selection of e (gcd(e,φ(n))) =1 must be observed
Efficient Decryption
- Exponentiation (with exponent d) used in RSA decryption
- The Chinese Remainder Theorem (CRT) for faster calculation, which involves computing separately (mod p and mod q) then combining the results.
- In RSA, decryption is slower than encryption primarily due to the large decryption exponent, and the significant computational cost to perform the large discrete log calculation or discrete logarithm.
RSA Key Generation
- RSA users must determine 2 primes at random - p and q
- Select either e or d and compute the other if the selection is made for the other.
- The prime numbers - p, and q, must not be easily derived from the modulus, n = p x q, leading to the requirement of sufficient size.
- Use the modular inverse algorithm to calculate the other exponent from a known exponent.
RSA Security
- Possible attacks include:
- Brute-force key search (infeasible due to large key sizes)
- Mathematical attacks (based on factoring difficulty of modulus n)
- Timing attacks (exploiting decryption timing variations).
- Chosen ciphertext attacks (exploiting RSA properties).
Factoring Problem
- The mathematical approach to attacking RSA involves factoring n, computing ø(n), and then determining d.
- Finding d directly is as hard as factoring, and so is computing ø(n)
- Current belief that factoring is equivalent to most RSA attacks
- Slow improvement over years of this attack, with the largest factors currently up to 663 bits
RSA Timing Attacks
- Exploiting variations in operation timing to infer operand size
- Using constant exponentiation time and introducing random delays with the addition of blind values is used to help thwart timing attacks
Chosen Ciphertext Attacks
- Attackers select ciphertexts to gain information about messages to assist in cryptanalysis
- Countermeasures, such as padding (add additional characters for encryption), are used for protection
Summary
- Includes RSA principles, implementation, and security concepts.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Explore the fundamentals of cryptography with a focus on private-key and public-key systems. Learn about their differences, functionalities, and security implications. This quiz will test your understanding of symmetric and asymmetric cryptography concepts.
