Public Key Cryptography: RSA Algorithm and Mathematical Concepts

This assignment delves into the realm of public-key cryptography, focusing on the RSA algorithm. It begins by addressing common misconceptions and outlining the principles of public-key cryptosystems, including key distribution and digital signatures. The document elucidates the components of a public-key encryption scheme, differentiating between secret key and public key characteristics, and exploring applications such as encryption/decryption, digital signatures, and key exchange. It also covers the requirements for public-key algorithms, emphasizing the role of trapdoor one-way functions. Furthermore, the assignment provides a detailed exploration of the mathematical ideas underlying RSA, including prime numbers, factorization, the greatest common divisor, modular arithmetic, and Euler's theorem. It then explains the RSA algorithm, its requirements, and provides a worked example, illustrating the encryption and decryption processes. This comprehensive overview provides a solid foundation for understanding the principles and practical applications of public-key cryptography.

Chapter 9
Public Key Cryptography and RSA
© 2017 Pearson Education, Ltd., All rights reserved.

Table 9.1
Terminology Related to Asymmetric Encryp
Source: Glossary of Key Information Security Terms, NIST IR 7298 [KISS06]
© 2017 Pearson Education, Ltd., All rights reserved.

Misconceptions Concerning
Public-Key Encryption
• Public-key encryption is more secure from
cryptanalysis than symmetric encryption
• Public-key encryption is a general-purpose
technique that has made symmetric
encryption obsolete
© 2017 Pearson Education, Ltd., All rights reserved.

• The concept of public-key cryptography evolved from
an attempt to attack two of the most difficult
problems associated with symmetric encryption:
• Whitfield Diffie and Martin Hellman from Stanford
University achieved a breakthrough in 1976 by com
up with a method that addressed both problems and
was radically different from all previous approaches
cryptography
Principles of Public-Key
Cryptosystems
• How to have secure communications in general without having to
trust a KDC with your key
Key distribution
• How to verify that a message comes intact from the claimed sende
Digital signatures
© 2017 Pearson Education, Ltd., All rights reserved.

Public-Key Cryptosystem
• A public-key encryption scheme has six ingredie
Plaintext
The
readable
message
or data
that is fed
into the
algorithm
as input
Encryption
algorithm
Performs
various
transforma-
tions on the
plaintext
Public key
Used for
encryption
or
decryption
Private key
Used for
encryption
or
decryption
Ciphertext
The
scrambled
message
produced
as output
Decryption
algorithm
Accepts
the
ciphertex
t and the
matching
key and
produces
the
original
plaintext
© 2017 Pearson Education, Ltd., All rights reserved.

Comparison of SK and PK
DISTINCT
FEATURES
SECRET KEY PUBLIC KEY
NUMBER OF
KEYS
Single key. Pair of keys.
TYPES OF KEYS Key is secret. One key is
private, and one
key is public.
SIZE OF KEY 50-250 bits 500-2500 bits
RELATIVE
SPEEDS
Faster. Slower.

© 2017 Pearson Education, Ltd., All rights reserved.

Table 9.2
Conventional and Public-Key Encry
© 2017 Pearson Education, Ltd., All rights reserved.

Public-Key Cryptosystem: Sec
© 2017 Pearson Education, Ltd., All rights reserved.

Public-Key Cryptosystem: Authentic
© 2017 Pearson Education, Ltd., All rights reserved.

Public-Key Cryptosystem:
Authentication and Secrecy
© 2017 Pearson Education, Ltd., All rights reserved.

Applications for Public-Ke
Cryptosystems
• Public-key cryptosystems can be classified into
three categories:
• Some algorithms are suitable for all three
applications, whereas others can be used only fo
one or two
•The sender encrypts a message
with the recipient’s public keyEncryption/decryption
•The sender “signs” a message
with its private keyDigital signature
•Two sides cooperate to
exchange a session keyKey exchange
© 2017 Pearson Education, Ltd., All rights reserved.