Cyber Security 101 -> Cryptography

Link: Cyber Security 101 > Cryptography
Difficulty: Easy
Date Completed: 2025-05-20

---

Public Key Cryptography Basics

Public Key Cryptography Basics

• authentication - you are confirming the identity of who you are talking with. You want to be sure you communicate with the right person, not someone else pretending.
• authenticity - you verify that the message genuinely comes from a specific sender. You can verify that the information comes from the claimed source.
• integrity - moreover, you know that what they are saying is reaching you, and there is no chance of anything changing the other party's words - i.e. ensuring that the data has not been altered or tampered with. You must ensure that no one changes the data you exchange.
• confidentiality - only the authorised parties can access the data. You want to prevent an unauthorised party from eavesdropping on your conversations.

Cryptography can provide solutions to satisfy the above requirements, among many others. Private key cryptography, i.e. symmetric encryption, mainly protects confidentiality. In public key cryptography, i.e. asymmetric cryptography, plays a significant role in authentication, authenticity, and integrity.

Learning Objectives:

• RSA
• Diffie-Hellman
• SSH
• SSL/TLS Cerfiticates
• PGP and GPG

RSA

RSA is a public-key encryption algorithm that enables secure data transmission over insecure channels. With an insecure channel, we expect adversaries to eavesdrop on it.

RSA is based on the mathematically difficult problem of factoring a large number. Multiplying two large prime numbers is straightforward operation; however, finidng the factors of a huge number takes much more computing power.

It's tricky to determine what two prime numbers multiply together to make 14351 and even more challenging to find the factors of 166764499494295486767649.

Numerical Example

Let's revisit encryption, decryption, and key usage in asymmetric encryption. The public key is known to all correspondents and is used for encryption, while the private key is protected and used for decryption.

1. Bob chooses two prime numbers: p = 157 and q = 199. He calculates n = p x q = 31243.
2. With ϕ(n) = n - p - q + 1 = 31243 - 157 - 199 + 1 = 30888, Bob selects e = 163 such that e is relatively prime to ϕ(n); moreover, he selects d = 379, where e x d = 1 mod ϕ(n), i.e., e x d = 163 * 379 = 61677, and 61677 mod 30888 = 1. The public key is (n,e), i.e., (31243, 163) and the private key is $(n,d), i.e., (31243, 379).
3. Let's say that the value they want to encrypt is x = 13, then Alice would calculate and send y = x^e mod n = 13^163 mod 31243 = 16341.
4. Bob will decrypt the received value by calculating x = y^d mod n = 16341^379 mod 31243 = 13. This way, Bob recovers the value that Alice sent him.

It is worth repeating that in this example, we picked a three-digit prime number, while in an actual application, p and q would be at least a 300-digit prime number each.

RSA in CTFs

The math behind RSA comes up relatively often in CTFs, requiring you to calculate variables or break some encryption based on them. Many good articles online explain RSA, and they will give you almost all of the information you need to complete the challenges. One good example of an RSA CTF challenge is the Breaking RSA room.

There are some excellent tools for defeating RSA challenges in CTFs. Some of the most popular ones are:

• RsaCtfTool
• rsatool

RSA variables

• p and q: are large prime numbers.
• n: is the product of p and q, i.e., n = p * q.
• The public key is (n, e), where e is a number that is relatively prime to ϕ(n).
• The private key is (n, d), where d is the modular multiplicative inverse of e mod ϕ(n).
• m: is used to represent the original message, i.e., the plaintext.
• c: represents the encrypted text, i.e., the ciphertext.

Diffie-Hellman Key Exchange

Key exchange aims to establish a shared secret between two parties. It is a method that allows two parties to establish a shared secret over and insecure communication channel without requiring a pre-exising shared secret and without an observer being able to get this key. Consequently, this shared key can be used for symmetric encryption in subsequent communications.

Consider the following scenario. Alice and Bob want to talk securly. They want to establish a shared key for symmetric cryptography but don't want to use asymmetric cryptography for the key exchange. This is where the Diffie-Hellman Key Exchange comes in.

Alice and Bob generate secrets independently; let's call these secrets A and B. They also have some public common material; let's call this C.

We need to make some assumptions. Firstly, whenever we combine secrets, they're practically impossible to separate. Secondly, the order in which they're combined doesn't matter. Alice and Bob will combine their secrets with the common material to form AC and BC. They will then send these to each other and combine the received part with their secret to create two identical keys, both ABC. Now, they can use this key to communicate.

Let's investigate the exact process:

1. Alice and Bob agree on the public variables: a large prime number p and a generator g, where 0 < g < p. These values will be disclosed publicly over the communication channel. Although insecurely small, we will choose p = 29 and g = 3 to simplify our calculations.
2. Each party chooses a private integer. As a numerical example, Alice chooses a = 13, and Bob chooses b = 15. Each of these values represents a private key and must not be disclosed.
3. It is time for each party to calculate their public key using their private key from step 2 and the agreed-upon public variables from step 1. Alice calculates A = g^a mod p = 3^13 mod 29 = 19 and Bob calculates B = g^b mod p = 3^15 mod 29 = 26. These are the public keys.
4. Alice and Bob send the keys to each other. Bob receives A = g^a mod p = 19, i.e., Alice's public key. And Alice receives B = g^b mod p = 26, i.e., Bob's public key. This step is called the key exchange.
5. Alice and Bob can finally calculate the shared secret using the received public key and their own private key. Alice calculates B^a mod p = 26^13 mod 29 = 10 and Bob calculates A^b mod p = 19^15 mod 29 = 10. Both calculations yield the same result, g^ab mod p = 10, the shared secret key.

Diffie-Hellman Key Exchange is often used alongside RSA public key cryptography. Diffie-Hellman is used for key agreement, while RSA is used for digital signatures, key transport and authentication among many others. For instance, RSA helps prove the identity of the person you're talking to via digital signing, as you can confirm based on their public key. This would prevent someone from attacking the connection with a man-in-the-middle attack against Alice by pretending to be Bob. In brief, Diffie-Hellman and RSA are incorporated into many security protocols and standards to provide a comprehensive security solution.

SSH

Authenticating the Server

If you have used an SSH client before, you would know the confirmation prompt in the terminal:

root@TryHackMe# ssh 10.10.244.173
The authenticity of host '10.10.244.173 (10.10.244.173)' can't be established.
ED25519 key fingerprint is SHA256:lLzhZc7YzRBDchm02qTX0qsLqeeiTCJg5ipOT0E/YM8.
This key is not known by any other name.
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added '10.10.244.173' (ED25519) to the list of known hosts.

In the above interaction, the SSH client confirms whether we recognise the server's public key fingerpting. ED25519 is the public-key algorithm used for digital signature generation and verification in this example. Our SSH client didn't recognise this key and is asking us to confirm whether we want to continue with the connection. This warning is because a man-in-the-middle attack is probable; a malicious server might have intercepted the connection and replied, pretending to be the target server.

Authenticating the Client

At some point, one will surely hit a machine with SSH configured with key authentication instead. This authentication uses public and private keys to prove the client is a valid and authorised user on the server. By default, SSH keys are RSA keys.

ssh-keygen is the program usually used to generate key paris. It supports various algorithms:

• 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 (Elliptic Curve Digital Signature Algorithm - Security Key) - is an extension of ECDSA. It incorporates hardware-based security keys for enhanced private key protection.
• Ed25519 (Edwards-Curve Digital Signature Algorithm) - is a public-key signature system using EdDSA with Curve25519.
• Ed25519-SK (Edwards-Curve Digital Signature Algorithm - Security Key) - is a variant of Ed25519. Similar to ECDSA-SK, it uses a hardware-based security key for improved private key protection.

Using SSH Keys to get a "Better Shell"

During CTFs, penetration testing and red teaming exercises, SSH keys are an excellent way to "upgrade" a reverse shell, assuming the user has login enabled. Note that www-data usually does not allow this, but regular users and root will work. Leaving an SSH key in the authorized_keys file on a machine can be a useful backdoor, and you don't need to deal with any of the issues of unstabilised revese shells like Control-C or lack of tab completion.

Digital Signatures and Certificates (skipped)

skipped for now

PGP and GPG

TIP

You may need to use GPG to decrypt files in CTFs. With PGP/GPG, private keys can be protected with passphrases in a similar way that we protect SSH private keys. If the key is passphrase protected, you can attempt to crack it using John the Ripper and gpg2john.

Hashing Basics (done but skipped content)

Hashing Basics

Learning Objectives:

• hash functions and collisions,
• the role of hashing in authentication systems,
• recognizing stored hash values,
• cracking hash values,
• the use of hashing for integrity protection

John the Ripper

John the Ripper Learning Objectives:

• cracking windows authentication hashes
• crack /etc/shadow hashes
• cracking password-protected Zip files
• cracking password-protected RAR files
• cracking SSH keys