Cryptography Basics

1. Introduction#

Cryptography is the study and practice of protecting information so that only the intended people can read or change it.

It helps create secure communication between computers even if attackers are present.

Cryptography is everywhere in our digital world:

• When you visit websites (HTTPS)
• When you send messages
• When you use online banking
• When you log in to accounts

2. Importance of Cryptography#

The main goals of cryptography are:

• Confidentiality: Keeping information secret so only authorised people can read it.
• Integrity: Ensuring data isn’t changed without permission.
• Authenticity: Verifying that people or systems are who they claim to be.

Everyday Examples#

• Logging into TryHackMe: Your password is encrypted when sent to the server.
• SSH connections: Data is encrypted so no one can spy on your session.
• Online banking: Your browser verifies the bank's identity with certificates.
• File downloads: Hashes verify the file was not altered.

Legal and Industry Requirements#

• Companies that handle credit cards must follow PCI DSS, requiring encryption for storing and sending data.
• Medical records have laws depending on the country:
  • HIPAA and HITECH in the USA
  • GDPR in Europe
  • DPA in the UK

Summary

Cryptography is not just about hiding secrets. It is a fundamental part of making the internet safe and trustworthy.

2. Plaintext to Ciphertext#

Before we look at the terms, let’s understand the basic process of encryption:

• Plaintext is the original, readable message or data.
  • Examples: "hello", a photo, credit card details, health records.
• The Encryption Function takes the plaintext and a key as input.
  • It outputs ciphertext, which is unreadable and scrambled.

Process:

Plaintext + Key --> Encryption Function --> Ciphertext

To read the original message again, you need to decrypt it:

• The Decryption Function takes the ciphertext and the key as input.
  • It returns the original plaintext.

Process:

Ciphertext + Key --> Decryption Function --> Plaintext

📌 Key Terms#

• Plaintext

  • The original readable message or data before encryption.

• Ciphertext

  • The unreadable, scrambled version after encryption.
  • Should give no information about the original data.

• Cipher

  • The algorithm used to convert plaintext to ciphertext and back.
  • Usually public knowledge, designed by mathematicians.

• Key

  • A secret string of bits used with the cipher.
  • Must be kept secret (unless it’s a public key in asymmetric encryption).

• Encryption

  • Converting plaintext into ciphertext using a cipher and a key.

• Decryption

  • Reversing encryption to get back the plaintext using the cipher and key.
  • Without the key, decrypting should be infeasible.

3. Historical Ciphers#

Cryptography is ancient. It has been used for thousands of years.

One famous historical cipher is the Caesar Cipher from the first century BCE.

📌 Caesar Cipher#

• Idea: Shift each letter in the plaintext by a certain number.
• Example:
  • Plaintext: TRYHACKME
  • Key: 3 (Shift right by 3)
  • Cipher: Caesar Cipher

Encryption Process:

T -> W
R -> U
Y -> B
H -> K
A -> D
C -> F
K -> N
M -> P
E -> H

Ciphertext: WUBKDFNPH

Decryption Process:

• Shift the letters back to the left by 3.
• You recover the original message.

⚠️ Why Is It Insecure?#

• The Caesar Cipher has only 25 possible keys (alphabet has 26 letters).
• An attacker can try all shifts (brute force) and find the original message easily.

📌 Other Historical Ciphers#

• Vigenère Cipher – 16th century
• Enigma Machine – World War II
• One-Time Pad – Cold War

These ciphers were important in history but have been replaced by modern, stronger methods.

Summary

Encryption turns readable data (plaintext) into unreadable data (ciphertext) using a cipher and a key. Decryption reverses this. Historical ciphers like Caesar’s are simple but insecure by today’s standards.

3. Types of Encryption (Short & Simple)#

There are two main types:

1. Symmetric Encryption#

• Same secret key used to encrypt and decrypt.
• Fast and efficient.
• Problem: How to share the secret key safely.

Examples:

• DES (old, insecure)
• 3DES (deprecated)
• AES (recommended, 128/192/256-bit keys)

Real-life example:
Locking a box with one key both people need.

2. Asymmetric Encryption#

• Uses two keys:
  • Public Key: Anyone can use to encrypt.
  • Private Key: Only you can use to decrypt.
• Solves the key-sharing problem.
• Slower, but better for secure exchange.

Examples:

• RSA
• Diffie-Hellman
• Elliptic Curve Cryptography (ECC)

Real-life example:
A mailbox:

• Anyone can drop letters inside (public key).
• Only you have the key to open it (private key).

** Summary:**

• Symmetric: Same key. Fast. Need secure sharing.
• Asymmetric: Two keys. Secure sharing. Slower.

6. RSA (Short & Simple)#

RSA is a public-key encryption method for sending data securely over insecure channels. It's widely used in secure communications.

Why RSA is Secure#

• Based on factoring big numbers.
• Easy to multiply two big primes.
• Hard to factor their product back into primes.

Example:

• Small primes: 113 × 127 = 14351 (easy to multiply)
• Harder example:
  • p = 982451653031
  • q = 169743212279
  • n = p × q = 166764499494295486767649 (hard to factor!)

In real RSA, these primes have hundreds of digits.

How RSA Works#

• Public Key: Known to everyone, used to encrypt.
• Private Key: Secret, used to decrypt.

Example process:

1. Alice encrypts message with Bob’s public key.
2. Bob decrypts it with his private key.

Numerical Example (Simplified)#

• Bob chooses:

  • p = 157, q = 199
  • n = p × q = 31243
  • ϕ(n) = (p−1) × (q−1) = 30888
  • e = 163 (public exponent)
  • d = 379 (private exponent, satisfies e×d ≡ 1 mod ϕ(n))

• Public key: (n, e) = (31243, 163)

• Private key: (n, d) = (31243, 379)

Encryption:

• Plaintext m = 13
• Ciphertext c = m^e mod n = 16341

Decryption:

• m = c^d mod n = 13

RSA in CTFs#

• Common challenge in CTFs (Capture The Flag competitions).
• You might be given:
  • p, q: primes
  • n: p × q
  • e: public exponent
  • d: private exponent
  • m: plaintext
  • c: ciphertext

Goal: Break the encryption and recover the message.

Tools:

• RsaCtfTool : https://github.com/RsaCtfTool/RsaCtfTool (opens in a new tab)
• rsatool : https://github.com/ius/rsatool (opens in a new tab)

** Summary**

• RSA is secure because factoring large numbers is hard.
• Public key for encryption, private key for decryption.
• Used everywhere from secure messaging to online banking.

🔐 RSA Challenge Walkthrough for CTFs#

When you see RSA challenges in CTFs, you often have to calculate or recover values like n, ϕ(n), d, and decrypt a ciphertext c.

This section explains step by step how to do these calculations, with formulas and tools you can use.

Step 1: Calculate n#

Formula:

n = p * q

Explanation:

• n is the modulus.
• p and q are large prime numbers.
• It's used in both public and private keys.

Example: p = 4391 q = 6659 n = 4391 * 6659 = 29239669

Step 2: Calculate ϕ(n)#

Formula:

ϕ(n) = (p - 1) * (q - 1)

Explanation:

• ϕ(n) is Euler’s totient function.
• Used to find the private exponent d.

Example:

ϕ(n) = (4391 - 1) * (6659 - 1)
ϕ(n) = 4390 * 6658 = 29228620

Step 3: Calculate d (the private exponent)#

If you have e (public exponent), find d such that:

(d * e) ≡ 1 (mod ϕ(n))

This is called the modular inverse.

How to compute it:

• Use Extended Euclidean Algorithm.
• In Python:

pow(e, -1, phi)

Example (given):

e = 65537
d = modular_inverse(e, ϕ(n))

Step 4: Decrypt the Ciphertext If you have ciphertext c, decrypt it:

m = c^d mod n

Where:

c = ciphertext d = private exponent n = modulus m = plaintext message

Example in Python:

m = pow(c, d, n)

Typical RSA CTF Challenge Flow Given p and q → Compute n and ϕ(n). Given e → Compute d using ϕ(n). Given c → Decrypt to get m.

Common Tools for RSA Challenges These tools make solving RSA challenges much easier:

RsaCtfTool

Automates factorisation, d calculation, decryption.

Command example:

python3 RsaCtfTool.py -n [n] -e [e] --uncipher [c]

rsatool Generate keys or inspect existing ones. factordb.com Website to factor small or known n values. SageMath Very powerful for custom scripts or algebra.

Notes for CTF Players Always check if n is small enough to factor with factordb.com. RsaCtfTool can sometimes crack weak keys automatically. Remember the variables:

p, q = prime factors n = modulus = p * q ϕ(n) = (p - 1) * (q - 1) e = public exponent d = private exponent c = ciphertext m = plaintext

Diffie-Hellman Key Exchange#

The Diffie-Hellman (DH) Key Exchange enables two parties to establish a shared secret over an insecure channel without prior shared secrets. It involves selecting a large prime ppp, a generator ggg, and exchanging partial results to ultimately compute the same secret key on both sides.

Steps:

Choose public values ppp and ggg. Each party selects a private key and calculates their public key. Both parties exchange public keys and compute the shared secret.

exemple :#

Answer the questions below

Consider p = 29, g = 5, a = 12. What is A?

Answer: 7

Calculate AAA: Formula: A=gamod pA = g^a \mod pA=gamodp Calculation: A=512mod 29A = 5^{12} \mod 29A=512mod29 Result: A=7A = 7A=7

Consider p = 29, g = 5, b = 17. What is B?

Answer: 9

Calculate BBB: Formula: B=gbmod pB = g^b \mod pB=gbmodp Calculation: B=517mod 29B = 5^{17} \mod 29B=517mod29 Result: B=9B = 9B=9

Knowing that p = 29, a = 12, and you have B from the second question, what is the key calculated by Bob? (key = Ba mod p)

Answer: 24

Calculate Bob's Key (using BBB and aaa): Formula: Key=Bamod p\text{Key} = B^a \mod pKey=Bamodp Calculation: Key=912mod 29\text{Key} = 9^{12} \mod 29Key=912mod29 Result: Key=24\text{Key} = 24Key=24 Knowing that p = 29, b = 17, and you have A from the first question, what is the key calculated by Alice? (key = Ab mod p)

Answer: 24

SSH Basics#

SSH (Secure Shell) is a protocol for securely accessing remote machines. It uses cryptography to ensure confidentiality, authenticity, and integrity. ssh-keygen is the program usually used to generate key pairs. It supports various algorithms, as shown on its manual page below.

🔑 Authenticating the Server#

When you connect with SSH for the first time, you see a warning about host authenticity.
The following is just for your information. At this stage, we recommend that you recognise their names only.

DSA (Digital Signature Algorithm) is a public-key cryptography algorithm specifically designed for digital signatures. ECDSA (Elliptic Curve Digital Signature Algorithm) is a variant of DSA that uses elliptic curve cryptography to provide smaller key sizes for equivalent security. ECDSA-SK (ECDSA with Security Key) is an extension of ECDSA. It incorporates hardware-based security keys for enhanced private key protection. Ed25519 is a public-key signature system using EdDSA (Edwards-curve Digital Signature Algorithm) with Curve25519. Ed25519-SK (Ed25519 with Security Key) is a variant of Ed25519. Similar to ECDSA-SK, it uses a hardware-based security key for improved private key protection. Commands:

ssh-keygen -t ALGORITHM: Generates a public and private key pair using a specified algorithm (e.g., RSA, ED25519). ssh -i PRIVATE_KEY user@host: Specifies a private key for SSH login.

PGP and GPG (Brief Overview)#

PGP (Pretty Good Privacy) is software for encrypting files, emails, and creating digital signatures.
GPG (GnuPG) is a free, open-source implementation of the OpenPGP standard.

🔑 What Is It For?#

• Encrypt messages or files so only the intended recipient can read them.
• Digitally sign messages or files to prove they are really from you and haven't been altered.

🔑 How Does It Work?#

• Key Pair:
  • Public Key: Share with others. They use it to encrypt messages for you.
  • Private Key: You keep secret. Used to decrypt messages or sign them.

🔑 Typical Use in Email#

• Encrypt your email for confidentiality.
• Sign your email for authenticity and integrity.
• Ensure the receiver knows it really came from you.

🔑 Generating Keys with GPG#

You can create your own key pair using:

gpg --full-generate-key

Choose type (RSA, ECC, etc.) Set expiry if you want. Add name and email info.

🔑 Example Use Share your public key with contacts. They encrypt messages with your public key. You decrypt them with your private key. You can sign files/emails so others know it's really you.

🔑 Importing/Backing Up Keys Export your key for backup and store it safely.

Import on new machines with:

gpg --import backup.key

Decrypt messages with:

gpg --decrypt confidential_message.gpg

Security Tip Protect your private key with a strong passphrase. Tools like John the Ripper can try to crack weak passphrases.