Public Key Cryptosystem Principles
Public key cryptography, also known as asymmetric cryptography, uses a pair of
mathematically related keys — a public key for encryption or signature verification, and
a private key for decryption or signing. This approach addresses the key distribution
problem in symmetric encryption and enables secure communication without pre-shared
secrets.
Core Principles:
Two-Key Mechanism:
One key encrypts, the other decrypts. Knowing the public key does not reveal the private key.
Computational Security: It is computationally infeasible to derive the private key
from the public key and algorithm alone.
Public Key Distribution: Public keys can be openly shared, enabling secure
communication with anyone.
Private Key Confidentiality: The private key must remain secret to maintain security.
Main Components:
Plaintext – Original readable message.
Encryption Algorithm – Converts plaintext into ciphertext using one key.
Public/Private Keys – Key pair generated for encryption/decryption.
Ciphertext – Unreadable scrambled output.
Decryption Algorithm – Recovers plaintext using the matching key.
RSA Algorithm Overview
RSA (Rivest–Shamir–Adleman) is an asymmetric cryptographic
algorithm used for secure data transmission.
It uses two keys:
Public Key: Shared with everyone (used for encryption).
Private Key: Kept secret (used for decryption).
Steps in RSA
1. Key Generation
o Choose two large prime numbers p and q.
o Compute n=p×q
o Compute Euler’s totient: φ(n)=(p−1) ×(q−1)
o Choose an integer e such that 1<e<φ(n) gcd (e, φ(n)) =1.
o Compute d as the modular multiplicative inverse
of e modulo φ(n): d×e≡1 (mod φ(n))
Public Key = (e, n)
Private Key = (d, n)
2. Encryption
o Cipher text:
C=Me mod n where M is the plaintext (as a number).
3. Decryption
o Plaintext:
M=Cd mod n
Diffie-Hellman algorithm:
The Diffie-Hellman algorithm is being used to establish a shared secret that can be
used for secret communications while exchanging data over a public network
secret key using the parameters.
For the sake of simplicity and practical implementation of the algorithm, we
will consider only 4 variables, one prime P and G (a primitive root of P) and
two private values a and b.
P and G are both publicly available numbers. Users (say Alice and Bob) pick
private values a and b and they generate a key and exchange it publicly. The
opposite person receives the key and that generates a secret key, after which
they have the same secret key to encrypt.
Step-by-Step explanation is as follows:
Alice Bob
Public Keys available = P, G Public Keys available = P, G
Private Key Selected = a Private Key Selected = b
Key generated = Key generated =
x=GamodP y=GbmodP
Exchange of generated keys takes place
Key received = y key received = x
Generated Secret Key = Generated Secret Key =
ka=yamodP kb=xbmodP
Algebraically, it can be shown that
ka=kb
Alice Bob
Users now have a symmetric secret key to encrypt
Example:
Step 1: Alice and Bob get public numbers P = 23, G = 5
Step 2: Alice selected a private key a = 4 and
Bob selected a private key b = 3
Step 3: Alice and Bob compute public values
Alice: x =(5^4 mod 23) = (625 mod 23) = 4
Bob: y = (5^3 mod 23) = (125 mod 23) = 10
Step 4: Alice and Bob exchange public numbers
Step 5: Alice receives public key y =10 and
Bob receives public key x = 4
Step 6: Alice and Bob compute symmetric keys
Alice: ka = y^a mod p = 10000 mod 23 = 18
Bob: kb = x^b mod p = 64 mod 23 = 18
Step 7: 18 is the shared secret.
Onion Routing:
Onion routing is a technique for anonymous communication that encrypts
messages in multiple layers and routes them through a series of network
Nodes.
Homomorphic encryption:
Homomorphic encryption is a cryptographic technique that allows computations to be performed
on encrypted data without needing to decrypt it first. This means that the data remains secure
and private even while being processed.