Day 4 Public Key Cryptography (PKC) and HD (Hierarchical Deterministic) Wallet

Self Intro:¶

Hello everyone! 👋

I’m Rohan Sai, back with Day 4 of my "120 Days of Blockchain Technology" series! 🚀

Today, we’re diving into Public Key Cryptography (PKC) - a fundamental cryptographic system used to secure blockchain transactions. PKC ensures that your data remains private and transactions are authentic, using a pair of public and private keys.

To bring this to life, I’ve built a fun project:
🔗 HD Wallet Generator
👉 Try it out here: HD Wallet Generator

This project helps you generate a seed phrase, derive private/public keys, and create Bitcoin and Ethereum addresses. It also supports QR code generation and secure wallet backup.

All thanks to PKC! 🔐

Explore, experiment, and share your feedback!

---

Did You Know?¶

HD wallets are a game-changer in cryptocurrency management. They allow you to generate multiple addresses from a single seed phrase, ensuring better security and flexibility for users managing a range of cryptocurrencies.

¶

Public Key Cryptography (PKC)¶

Introduction and Basics of Public Key Cryptography¶

---

1. Introduction to Public Key Cryptography¶

Definition:
Public Key Cryptography (PKC), also known as asymmetric cryptography, is a cryptographic method that uses two different but mathematically linked keys:

• Public Key: Shared openly and used for encryption or signature verification.
• Private Key: Kept secret and used for decryption or signing.

Purpose:
PKC enables secure communication and authentication over insecure channels like the internet. It eliminates the need for both parties to share a common secret key beforehand, unlike symmetric cryptography.

---

2. Key Features of Public Key Cryptography¶

1. Asymmetry:

   • Unlike symmetric cryptography, PKC uses two distinct keys: one for encryption and another for decryption.

2. One-Way Functions:

   • Relies on mathematical problems that are easy to compute in one direction but computationally infeasible to reverse without specific information (e.g., factorization of large numbers, discrete logarithms).

3. Non-repudiation:

   • Digital signatures in PKC ensure that the sender of a message cannot deny having sent it.

4. Public-Private Key Pair:

   • Public key can be shared with anyone, but the private key must remain confidential to maintain security.

---

3. How Public Key Cryptography Works¶

1. Key Generation:

   • A cryptographic algorithm generates a pair of keys: public and private. The keys are mathematically related, ensuring data encrypted by one key can only be decrypted by the other.

2. Encryption:

   • The sender encrypts the message using the recipient's public key. Only the recipient, possessing the corresponding private key, can decrypt it.

3. Decryption:

   • The recipient decrypts the message using their private key.

4. Digital Signatures:

   • A sender signs a message using their private key. The recipient verifies the authenticity using the sender's public key.

---

4. Real-World Analogy¶

Imagine a lockbox with two keys:

• The public key acts like a key to lock the box, which anyone can use to secure a message.
• The private key acts like a unique key to unlock the box, which only the owner can use to access the message.

---

5. Mathematical Basis of Public Key Cryptography¶

Public key cryptography is grounded in number theory and complex mathematical operations. Key cryptographic operations involve:

1. Modular Arithmetic:

   • Operations within a finite set of integers, e.g., $ x \mod n $.

2. Prime Factorization:

   • Used in RSA; it is computationally difficult to factorize a large composite number into its prime components.

3. Discrete Logarithms:

   • Used in algorithms like Diffie-Hellman and ECC.

4. Elliptic Curve Mathematics:

   • Provides security with smaller keys using elliptic curves over finite fields.

---

6. Types of Public Key Cryptography Systems¶

1. Encryption Systems:

   • Use public-private keys for secure message transmission (e.g., RSA).

2. Signature Systems:

   • Enable digital signatures for authentication (e.g., DSA, ECDSA).

3. Key Exchange Systems:

   • Securely exchange symmetric keys over insecure channels (e.g., Diffie-Hellman, ECDH).

---

7. Key Applications of Public Key Cryptography¶

1. Secure Communication:

   • Encrypts sensitive data exchanged over the internet (e.g., HTTPS).

2. Digital Signatures:

   • Authenticate the sender's identity and ensure data integrity (e.g., signing emails).

3. Certificate Authority (CA):

   • Validates public keys through digital certificates (used in SSL/TLS).

4. Blockchain Technology:

   • Ensures secure transactions via signing and verifying blocks.

---

Types and Algorithms of Public Key Cryptography¶

1. Key Algorithms in Public Key Cryptography¶

---

1.1 RSA (Rivest–Shamir–Adleman)¶

Overview:

• One of the first widely used public key cryptosystems.
• Based on the mathematical challenge of prime factorization.

How It Works:

1. Key Generation:

   • Select two large prime numbers, $ p $ and $ q $.
   • Compute $ n = p \times q $ (the modulus).
   • Calculate $ \phi(n) = (p-1) \times (q-1) $ (Euler's totient function).
   • Choose $ e $ such that $ 1 < e < \phi(n) $ and $ gcd(e, \phi(n)) = 1 $.
   • Compute $ d $ such that $ e \times d \equiv 1 \mod \phi(n) $.
     • $ d $ is the modular multiplicative inverse of $ e $.

   Public Key: $ (e, n) $
   Private Key: $ (d, n) $

2. Encryption:

   • Ciphertext: $ c = m^e \mod n $, where $ m $ is the plaintext message.

3. Decryption:

   • Plaintext: $ m = c^d \mod n $.

Example:

• Public key: $ (e = 7, n = 33) $
• Private key: $ (d = 3, n = 33) $
• Encrypt $ m = 4 $: $ c = 4^7 \mod 33 = 16 $.
• Decrypt $ c = 16 $: $ m = 16^3 \mod 33 = 4 $.

Applications: Secure email (PGP), digital certificates.

---

1.2. ElGamal Encryption¶

Overview:
ElGamal is an asymmetric encryption algorithm based on the Diffie-Hellman key exchange and is used for both encryption and digital signatures.

Process:

1. Key Generation:

   • Select a large prime $ p $ and a generator $ g $.
   • Choose a private key $ x $ and compute the corresponding public key $ h = g^x \mod p $.

2. Encryption:

   • To encrypt a message $ M $, choose a random integer $ k $, and compute:
     • $ y_1 = g^k \mod p $
     • $ y_2 = M \times h^k \mod p $

3. Decryption:

   • The recipient computes the shared secret $ s = y_1^x \mod p $ and retrieves the plaintext message:
     • $ M = y_2 \times (s^{-1}) \mod p $.

Advantages:

• Provides both encryption and digital signature capabilities.
• Highly secure due to the difficulty of solving discrete logarithms.

Disadvantages:

• Slower than RSA.
• Requires larger key sizes for similar security levels.

---

1.3 Diffie-Hellman Key Exchange¶

Overview:

• A method for securely exchanging cryptographic keys over a public channel.
• Based on the discrete logarithm problem.

How It Works:

1. Publicly agree on a prime $ p $ and a base $ g $ (generator).
2. Alice chooses a private key $ a $ and computes $ A = g^a \mod p $.
3. Bob chooses a private key $ b $ and computes $ B = g^b \mod p $.
4. Exchange $ A $ and $ B $ over the public channel.
5. Compute the shared secret:
   • Alice: $ s = B^a \mod p $.
   • Bob: $ s = A^b \mod p $.

Example:

• Public values: $ p = 23, g = 5 $.
• Alice's private key: $ a = 6 $, $ A = 5^6 \mod 23 = 8 $.
• Bob's private key: $ b = 15 $, $ B = 5^{15} \mod 23 = 19 $.
• Shared secret: $ s = 19^6 \mod 23 = 2 $.

Applications: Establishing secure connections (e.g., TLS).

---

1.4 Elliptic Curve Cryptography (ECC)¶

Overview:

• A modern public key cryptosystem offering strong security with smaller key sizes.
• Based on the mathematics of elliptic curves over finite fields.

Elliptic Curve Equation:
$ y^2 = x^3 + ax + b \ (\text{mod } p) $
Where $ a $ and $ b $ are constants, and $ p $ is a prime number.

How It Works:

1. Define an elliptic curve and a generator point $ G $.
2. Generate private key $ k $.
3. Compute public key: $ P = kG $ (scalar multiplication).

Example:

• Curve: $ y^2 = x^3 + 2x + 3 \ ( \mod 97 ) $.
• Generator point $ G = (3, 6) $.
• Private key $ k = 20 $, public key $ P = 20G = (x, y) $.

Applications: Bitcoin, secure messaging (Signal protocol).

Advantages:

• Smaller key sizes for equivalent security (e.g., 256-bit ECC ≈ 3072-bit RSA).

---

1.5 Digital Signature Algorithm (DSA)¶

Overview:

• A method for digitally signing and verifying data authenticity.
• Based on modular arithmetic and discrete logarithms.

How It Works:

1. Key Generation:

   • Choose prime $ p $ and $ q $ (a divisor of $ p-1 $).
   • Select $ g = h^{(p-1)/q} \mod p $.
   • Private key: $ x $, $ 1 < x < q $.
   • Public key: $ y = g^x \mod p $.

2. Signature:

   • Compute $ r = (g^k \mod p) \mod q $.
   • Compute $ s = k^{-1} (H(m) + xr) \mod q $.

3. Verification:

   • Compute $ w = s^{-1} \mod q $.
   • Validate $ u_1 = H(m)w \mod q $ and $ u_2 = rw \mod q $.
   • Check $ v = ((g^{u_1}y^{u_2}) \mod p) \mod q $.

Applications: Secure authentication, document verification.

---

2. Comparison of Public Key Algorithms¶

Algorithm	Key Size	Security Basis	Applications
RSA	Large (2048+)	Prime factorization	Encryption, signatures
Diffie-Hellman	Moderate	Discrete logarithm	Key exchange
ECC	Small	Elliptic curve mathematics	Blockchain, IoT
DSA	Moderate	Discrete logarithm	Digital signatures

---

Public Key Cryptography in Practice and Code Implementation :¶

1. Applications of Public Key Cryptography¶

1.1. Secure Communication
Public key cryptography ensures the confidentiality of data transmitted over insecure channels, such as the internet. Examples include:

• TLS/SSL: Secures websites via HTTPS.
• Email Encryption: Protocols like PGP (Pretty Good Privacy) or S/MIME.

1.2. Digital Signatures
Digital signatures provide integrity, authenticity, and non-repudiation of data.

• Process:
  • The sender signs a message using their private key.
  • The recipient verifies the signature using the sender's public key.
• Examples: Blockchain transactions, document verification.

1.3. Key Management and Distribution

• Public key cryptography simplifies key management by eliminating the need for securely sharing symmetric keys.
• Used in protocols like Diffie-Hellman for secure key exchange.

1.4. Cryptocurrencies and Blockchain

• Public key cryptography underpins blockchain technology, enabling secure transactions and wallet addresses.

---

2. Implementation Examples¶

2.1 RSA Implementation in Python¶

Using the cryptography library:

from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes

# Generate RSA keys
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
)

public_key = private_key.public_key()

# Serialize keys
private_pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.NoEncryption(),
)

public_pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)

print("Private Key:\n", private_pem.decode())
print("Public Key:\n", public_pem.decode())

# Encrypt message
message = b"Hello, RSA!"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

# Decrypt message
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Plaintext:", plaintext.decode())

---

2.2 Diffie-Hellman Key Exchange in Python¶

Using the cryptography library:

from cryptography.hazmat.primitives.asymmetric import dh
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate private keys
private_key_1 = parameters.generate_private_key()
private_key_2 = parameters.generate_private_key()

# Generate public keys
public_key_1 = private_key_1.public_key()
public_key_2 = private_key_2.public_key()

# Exchange keys to compute shared secret
shared_key_1 = private_key_1.exchange(public_key_2)
shared_key_2 = private_key_2.exchange(public_key_1)

# Derive a key
derived_key_1 = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b'handshake data',
).derive(shared_key_1)

derived_key_2 = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b'handshake data',
).derive(shared_key_2)

assert derived_key_1 == derived_key_2  # Verify shared keys match
print("Derived Key:", derived_key_1)

---

2.3 ECC Implementation in Python¶

Using the cryptography library:

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import serialization

# Generate ECC private key
private_key = ec.generate_private_key(ec.SECP256R1())

# Get public key
public_key = private_key.public_key()

# Serialize keys
private_pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.NoEncryption(),
)

public_pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)

print("Private Key:\n", private_pem.decode())
print("Public Key:\n", public_pem.decode())

---

3. Benefits and Drawbacks¶

Benefits:

• Eliminates the need for secure key distribution.
• Enables secure communication over insecure channels.
• Provides data integrity and authenticity.

Drawbacks:

• Computationally intensive compared to symmetric encryption.
• Vulnerable to quantum computing advancements (post-quantum cryptography is an area of active research).
• Requires careful implementation to avoid vulnerabilities.

---

4. Future of Public Key Cryptography¶

• Post-Quantum Cryptography: Development of algorithms resistant to quantum attacks, such as lattice-based cryptography.
• Integration with Emerging Technologies: Blockchain, IoT, and secure multiparty computation.
• Optimization for Efficiency: More efficient key generation and encryption methods for resource-constrained devices.

---

That’s a wrap for today! Check out the HD Wallet Generator here: 👉 HD Wallet Generator.

For more updates, follow me on LinkedIn and X. Stay curious, keep learning, and see you tomorrow for Day 5! 🚀✨

LinkedIn: Rohan Sai
X: RohanSai2208