Asymmetric Cryptography Basics

Requirements in the cyber realm:

• Authenticity: Ensure you are communicating with the right person and verify the source of information.
• Integrity: Ensure that no one alters the data you exchange.
• Confidentiality: Prevent eavesdropping on the conversation.

Cryptography provides a way to satisfy these requirements.

Secure Key Exchange

Symmetric cryptography is faster, but both parties need the same secret key. Asymmetric cryptography allows them to exchange a session key securely, after which they switch to symmetric cryptography for speed.

Encryption for Confidentiality

A sender encrypts a message with the recipient's public key. Only the recipient, with the corresponding private key, can decrypt it.

Digital Signatures

The sender signs data with their private key. Anyone can verify the signature using the sender's public key. This provides authentication, integrity, and non-repudiation.

Authentication

Systems can prove their identity using public/private key pairs instead of passwords. Example: SSH login with key-based authentication.

Digital Certificates

Used in SSL/TLS for HTTPS, digital certificates prove website authenticity and enable secure encrypted connections. Public key cryptography is at the core of this trust system.

Cryptocurrency and Blockchain

Users have private keys to sign transactions and public keys that others use to verify them. This ensures ownership, prevents tampering, and secures blockchain transactions.

In short, asymmetric cryptography enables secure communication, authentication, and verification, making it indispensable in today's interconnected world.

RSA is a public-key cryptography algorithm used to secure data. Its security comes from the difficulty of factoring very large numbers (multiplication is easy, factoring back is hard). Typical key sizes are 1024, 2048, 3072, or 4096 bits (roughly 309, 617, 925, and 1234 digits). The prime numbers used are about half that size.

The modulo operation gives the remainder after division. The symbol % is used. Example: 151 ÷ 50 = 3 remainder 1, so 151 % 50 = 1. Another example: 7428 % 536 = 460. For calculations in the example below, you can use Wolfram Alpha.

We'll follow the classic analogy of Bob and Alice:

1. Bob chooses two prime numbers: p = 10007 and q = 99991. He calculates n = p * q = 1000609937.

2. He computes Euler's totient: T = (p-1)(q-1) = 1000499940.

3. Bob chooses e, a number relatively prime to T. A common choice is 65537.

4. He calculates d such that (e * d) % T = 1. In this case, d = 662506613.

5. The public key is (n, e) = (1000609937, 65537). The private key is (n, d) = (1000609937, 662506613).

6. Suppose Alice wants to send a secret number x = 14082007. She computes y = x^e % n. Using Bob's public key, she gets y = 14082007⁶⁵⁵³⁷ % 1000609937 = 306497210.

7. Bob decrypts the ciphertext with his private key: x = y^d % n. So x = 306497210^662506613 % 1000609937 = 14082007.

In this way, the message is safely transmitted and unreadable by any third party—without ever sending private keys over the network.

Key exchange aims to establish a shared secret between two parties over an insecure communication channel without requiring a pre-existing shared secret and without third parties being able to obtain the message.

How it works

1. Alice and Bob agree on public variables: a large prime number p and a generator g, 0 < g < p. These values are publicly disclosed over the communication channel. Let's pick p = 999983 and g = 101. They are way too small for any real security.

2. Each party chooses a private integer. Let's say Alice picks a = 12345 and Bob picks b = 54321. These are private keys and must not be disclosed.

3. They each calculate their public key using their private key and public variables: Alice calculates A = g^a % p, and Bob calculates B = g^b % p. (Actual numbers require modular exponentiation and are too large to compute manually.)

4. Alice and Bob exchange the public keys. Bob receives A and Alice receives B. This step is called the key exchange.

5. Finally, they calculate the shared secret using the received public key and their private key: Alice calculates s = B^a % p, and Bob calculates s = A^b % p. Both computations produce the same shared secret. (Exact values require modular exponentiation due to large exponents.)