Benyam Seifu

Symmetric Key Cryptography

• it called symmetric because both the parties(encrypting and decrypting parties) have the SAME keys.

• usually used in military.

• good example is the classic Cesar Cypher ex: message = “abc” key=1(move one step to the right) , encrypted value = “bcd”

• a really good example in modern day is AES(Advanced Encryption Standard).

• down side of Symmetric key cryptography is both sides must have the key beforehand.

• What’s AES and how is it different from Cesar Cypher?

• Okay, so both AES and Cesar Cypher are symmetric key cryptography. But what makes AES different is as the name suggests it is advanced way of symmetric encryption. You may ask how it is advanced?

• So, here is how AES works:
  by taking a block of data, typically 128 bits(16 bytes) in size, and applying a series of mathematical operations called rounds. Each round involves substituting bytes, shifting rows, mixing columns and adding a round key.

  You might ask what’s the purpose of adding a round key on each rounds?

  • because, it adds an extra layer of randomness and uniqueness to the encrypted data. In AES, the round key is derived from original secret key and undergoes a specific transformation for each round. By adding the round key, AES ensures that even a small change in the original key will produce a completely different set of round keys. This property is crucial for achieving confusion and diffusion– the two fundamental principles in cryptography. Confusion means making the relationship between the plaintext and the ciphertext complex, while Diffusion spreads the infulence of each plaintext bit throughout the entire ciphertext.

Asymmetric Key Cryptography(Public Key Cryptography)

• born of inspiration of splitting a key in two by Whit Diffie in 1970s. Cryptographers at the time laughed it off.

• splitting a key in to two, has this 2 amazing usecases.

1. Authentication: one signs the other verifies.

   • So, the Authentication bit works like this. Bini will have is private and public key. Shares his public key to the world, and signs/authenticates a message with his private key, and
     anyone with Bini's public key can verify that message was indeed from Bini.

   • this gonna be very similar how look at this in Web3, so when u sign a transaction with your private key and you broadcast it to a blockchain, the blockchain nodes can recover your public key from the signature from which user’s address is derived. So, you sign a transaction then broadcast it to blockchain then the nodes in the blockchain can verify yes that is this person who authenticated this message.

   

2. Encryption: One key encrypts, the other decrypts.

• So, here is how the encryption bit goes. Bini will have his private and public key. Then Bini will share his public key and if Heni wants send a secure message only Bini can see, what Heni will do is, – grab Bini's public key, signs a the message with the public key and only Bini can decrypt the message using his private key. So, other’s cannot see the message.

_Start Thought Experiment 🧠

Let’s say there is a private key that can decrypt a message from a public key and vice-versa. Each key is the only key that can decrypt a message encrypted by the other key.

Authentication/digital signature bit of Public key cryptography

Now imagine Bob has declared a public key far and wide as the key that identifies him. Bob will keep a private key that corresponds to his public key. When he uses his private key to encrypt a message, he can share it publicly to be decrypted using his public key. Upon decrypting this message, we can say beyond the shadow of a doubt that only Bob could have written this message. The only key that could have encrypted the message is the corresponding private key which only Bob has access to. In practice, this would create an unforgeable digital signature for Bob.

Encryption bit of Public key cryptography

On the flip side, what if a message was encrypted using Bob’s public key? Of course, anyone can do this since Bob’s public key is available to everyone. The benefit comes in that only Bob can decrypt the message. In this way, a friend of Bob’s can write a message that can only be read by Bob. They could send it through any network, regardless of its security so long as it reaches Bob. They could rest assured that nobody would be able to decrypt the message except for Bob.

End Thought Experiment 🧠_

☝️ This was the insight that struck Whitfield Diffie in 1976. The only problem was, he didn’t have any practical way to make this happen. He had a concept, but he did not have a mathematical function with these properties! Diffie would work with both Martin Hellman and Ralph Merkle in search of such a system

• public key cryptography is considered asymmetric key cryptography because only one party has access to the private key.

RSA and ECDSA

• RSA and ECDSA are the two popular public key cryptography algorithms.

• How does RSA and ECDSA differ? One plays the both encryption and authentication role and the other only plays authentication role. RSA is used for encryption as well as authentication/digital signature and ECDSA is used authentication (BIG THING)

• The RSA algorithm is based on the idea that it's very easy to find the product of two prime numbers, yet extremely difficult to factor out those two prime numbers if you have the product.

📖 The Mathematics behind these algorithms can be quite difficult to wrap your brain around! How difficult the RSA algorithm is to decrypt is still an unsolved mystery in Computer Science. It’s assumed it can only be decrypted in exponential time (relative to the size of the input), which essentially boils down to a brute-force attack of randomly guessing at the key.

• ECDSA is a method used for ensuring the authenticity and integrity of digital data. It is based on the mathematics of elliptic curves.

• ECDSA algorithm uses elliptic curves. It can provide the same level security as other public key algorithms with smaller key sizes, which is the reason it's become quite popular. It is the Digital Signing Algorithm used by Bitcoin, specifically the secp256k1 curve.

• ECDSA works like a digital signature for electronic messages. Just as you would sign your name on a physical document to prove it’s authentic, ECDSA generates a unique signature for digital data

• Here is how ECDSA works:

1. Key Generation: first, a person generates a pair of related keys-- a private key and public key.

2. Signature Generation: when the person wants to sign a message, they use their private key and a specific algorithm to create a digital signature. The algorithm involves performing calculations based onn elliptic curves, which provide a secure way to generate the signature.

3. Signature verification: anyone who receives the signed message can verify its authenticity using the public key associated with the private key. They apply the verification algorithm, which involves comparing the original message, the received signature and the public key. If everything matches, it means the message hasn’t been tampered with, and the person with the corresponding private key signed it.

• if you ask this question again someday in the future– “Okay i got confused about the receiver knowing the original message“(understood this after a while, btw ECDSA is used to prove authencity and integrity of a message. It’s Authentication usecase of public key cryptography)

_Answer: when verifying the signature using ECDSA, the original message is not explicitly transmitted alongside the signature. Instead, it is assumed that the original message is already known by the receiver through some other means.

In most scenarios, the message itself is sent separately, and the receiver obtains both the message and its associated signature. the process of signature verification involves the following steps:

1. the receiver has the original message, the received signature, and the public key of the signer.

2. Using the public key, the receiver applies the verification algorithm, which involves mathematical computations based on elliptic curves. These computations help determine whether the signature is valid for a the given message.

3. The verification algorithm checks if the signature matches the provided public key and the message. it confirms that the signature was indeed created using the private key corresponding to the public key.

To summarize, the original message is assumed to be known by the receiver before the signature verification takes place. The receiver uses the public key and the received signature to confirm that the message hasn’t been tampered with and that it was indeed signed by the expected sender._

• How does RSA work?

• is an encryption algorithm used for secure communication and data protection.

• Here is how it works:

  1. Key generation: first, a person generates pair of related keys++ a public key and private key.

  2. Encryption: if someone wants to send encrypted message to the person with the public key, they use the public key to encrypt the message The encryption process involves perfoming mathematical operations on the message using the public key's parameters.

  3. Decryption: the person receiving the encrypted message uses their private key to decrypt it. Only the private key holder can perform the specific mathematical operations required to reverse the encryption and retrieve the original message.

  4. Digital Signatures: RSA can also be used for digital signatures like ECDSA.

• RSA's security is based on the mathematical difficulty of factoring large numbers into their prime factors. The larger the numbers used in RSA, the more secure it becomes, as factoring becomes computationally impractical.

• ECDSA is provides several advantages. it offers strong security while using shorter key lengths. this makes it efficient for mobile and resource-constrained devices.

Task - 2: Public Key Cryptography

_Let’s learn public key cryptography by applying it! 💪

In this series of exercises we will be focused on Public Key Cryptography with ECDSA (Elliptic Curve Digital Signature Algorithm). The specific algorithm we will use is secp256k1, which is the curve used for both Bitcoin and Ethereum. All points on this curve are valid bitcoin or ethereum public keys.

This set of code exercises will be instrumental towards understanding how we can use public key cryptography throughout the rest of the course.

• You will learn

1. how to sign a hashed message,
2. recover the public key from the signature and transform the public key into the user's ethereum address.

These concepts will help us understand how the blockchain protocol works and provide us with the tools to use digital signature authentication when we need to prove a user’s intention. This will be crucial knowledge when building applications interacting with blockchain as well as smart contracts on the blockchain.

Let’s jump in!_

step 1: Hashing Messages
The first step in ECDSA is to hash the message before applying the signature algorithm. So if you wanted to sign a message with one your keypairs saying that you "Vote Yes on Proposal 327", the first step would be to hash this message:

// turn this into an array of bytes, the expected format for the hash algorithm
const bytes = utf8ToBytes('Vote Yes on Proposal 327');
// hash the message using keccak256
const hash = keccak256(bytes);

console.log(toHex(hash)); // 928c3f25193b338b89d5646bebbfa2436c5daa1d189f9c565079dcae379a43be

You could ask why hash first? Because, that hash is 1 to 1 representation of the message(‘Vote Yes on Proposal 327’)

_☝️ After we have the message hash we can sign it with our private key to prove that a particular address votes yes on proposal 327. You may have found yourself doing something similar if you have ever signed a message in web3. When you send a transaction to a blockchain you also sign a hashed representation of that transaction before sending it to a blockchain node._

Answer:

// hashMessage.js
const { keccak256 } = require('ethereum-cryptography/keccak');
const { utf8ToBytes } = require('ethereum-cryptography/utils');

function hashMessage(message) {
    return keccak256(utf8ToBytes(message));
}

module.exports = hashMessage;

Step 2: Signing the Hash

It’s time to sign a message using our private key to prove our intention!

When signing a message with secp256k1 we can return the signature along with the recovery bit, allowing us to recover the public key from the signature. This will allow a blockchain node to take a signature of a transaction and understand which address authenticated this particular transaction.

💭 This is an important point, a blockchain transaction not only indicates the intent of the person who signed it, it also authenticates them through public key cryptography! We’ll see this more clearly when start signing transactions in future lessons.

🏁 Your Goal: Sign Message
Let’s sign a message!

First step is to hash it using the hashMessage function you created in the last stage (we’ve already imported it for you on line 2)

Once you have the message hash, use the sign method from the noble-secp256k1

_Note
The sign method will take your message hash along with the constant PRIVATE*KEY declared at the top of the file. This private key is a valid key that could be used to authorize blockchain transactions. Never use this specific key because it is published on the internet, so many people including yourself could authenticate with this specific private key. In future lessons we’ll be discussing good private key hygiene to avoid losing funds._

The sign method takes an optional third parameter called options, which you’ll see in the documentation. Use this parameter to return the recovered bit so that the public key can be recovered from this signature.

Side note about Recovery bit on ECDSA

ECDSA: Public Key Recovery from Signature

It is important to know that the ECDSA signature scheme allows the public key to be recovered from the signed message together with the signature. The recovery process is based on some mathematical computations (described in the SECG: SEC 1 standard) and returns 0, 1 or 2 possible EC points that are valid public keys, corresponding to the signature. To avoid this ambiguity, some ECDSA implementations add one additional bit v to the signature during the signing process and it takes the form {r, s, v}. From this extended ECDSA signature {r, s, v} + the signed message, the signer’s public key can be restored with confidence.

The public key recovery from the ECDSA signature is very useful in bandwidth constrained or storage constrained environments (such as blockchain systems), when transmission or storage of the public keys cannot be afforded. For example, the Ethereum blockchain uses extended signatures {r, s, v} for the signed transactions on the chain to save storage and bandwidth.

_Public key recovery is possible for signatures, based on the ElGamal signature scheme (such as DSA and ECDSA)._

• Very important resource for cryptography
  https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages#ecdsa-public-key-recovery-from-signature

Details

Using options to return a recoveryBit

The syntax for the third optional parameter of the secp sign function is a little tricky to get right… here’s how to properly use the third parameter in order to return a recoveryBit from the signature process - which will later be used to recover a public key using just the messageHash, signature, and recoveryBit:

return secp.sign(messageHash, PRIVATE_KEY, { recovered: true });

Just include the third parameter in an object that has the recovered key set to true. ✅

//singMessage.js
const secp = require('ethereum-cryptography/secp256k1');
const hashMessage = require('./hashMessage');

const PRIVATE_KEY =
    '6b911fd37cdf5c81d4c0adb1ab7fa822ed253ab0ad9aa18d77257c88b29b718e';

async function signMessage(msg) {
    return secp.sign(hashMessage(msg), PRIVATE_KEY, {
        recovered: true,
    });
}

module.exports = signMessage;

// test.js

const signMessage = require('../signMessage');
const hashMessage = require('../hashMessage');
const { assert } = require('chai');
const secp = require('ethereum-cryptography/secp256k1');
const { toHex } = require('ethereum-cryptography/utils');

const PRIVATE_KEY =
    '6b911fd37cdf5c81d4c0adb1ab7fa822ed253ab0ad9aa18d77257c88b29b718e';

describe('Sign Message', () => {
    it('should return both a signature and a recovery bit', async () => {
        const response = await signMessage('hello world');

        const errMessage =
            'expected signMessage to return both a signature and recovery bit!';
        assert(response.length, errMessage);
        assert(response.length === 2, errMessage);

        const [signature, recoveryBit] = response;
        assert(signature.length, 'expected signature to be a Uint8Array');
        assert(
            typeof recoveryBit === 'number',
            'expected the recovery bit to be a number'
        );
    });

    it('should have been signed by the same private key', async () => {
        const [sig, recoveryBit] = await signMessage('hello world');
        const messageHash = hashMessage('hello world');
        const recovered = secp.recoverPublicKey(messageHash, sig, recoveryBit);

        const publicKey = secp.getPublicKey(PRIVATE_KEY);
        assert.equal(toHex(recovered), toHex(publicKey));
    });
});

Step 3: Recover the Public Key

When the signature is passed with all of its components (recovery bit included), the public key can be recovered. This means that blockchain nodes will be able to understand who signed the transaction that was sent to them. A transaction could indicate the user would like to send 1 ether to another address and provide a certain transaction fee. Since the signature signs the hash containing this intention, it is enough to authenticate this action entirely.

🏁 Your Goal: Recover the Key
Given a message, signature, and recoveryBit find the public key and return it! Be sure to hash the message when passing it to the recovery method.
Use the noble-secp256k1 library documentation to find the correct method and parameters for this one.

Remember to check version 1.7.1 of the library’s documentation!

Ans:

const secp = require('ethereum-cryptography/secp256k1');
const hashMessage = require('./hashMessage');

async function recoverKey(message, signature, recoveryBit) {
    return secp.recoverPublicKey(hashMessage(message), signature, recoveryBit);
}

module.exports = recoverKey;

Step 4: Public Key to Address

Bitcoin and Ethereum both have a transformation process to take a public key and turn it into an address. For Bitcoin it includes a checksum and Base58 encoding. Ethereum's address transformation is quite a bit simpler, its address is the last 20 bytes of the hash of the public key.

The important thing to recognize here is that the address is differentiated from the public key, but you can always derive the address if you have the public key.

🏁 Your Goal: Get Ethereum Address
Let’s get the ethereum address from the public key!

First step, you’ll need to take the first byte off the public key. The first byte indicates the format of the key, whether it is in the compressed format or not. The publicKey will be a Uint8Array so you can use the slice method to slice off the first byte.
Next, take the keccak hash of the rest of the public key.
Finally, take the last 20 bytes of the keccak hash and return this. Once again, you can make use of the slice method.

Ans:

// getAddress.js
const secp = require('ethereum-cryptography/secp256k1');
const { keccak256 } = require('ethereum-cryptography/keccak');

function getAddress(publicKey) {
    // slice first byte because Uint8Array is an array of 8 bit(1 byte), unsigned integers
    const slicedPublicKey = publicKey.slice(1); // because the first byte contains metadata only
    const keccak256HashByteArray = keccak256(slicedPublicKey);
    // take the last 20 bytes from keccak256HashByteArray, you can use this alogrith to take last of what ever
    // say you want to get the last 2 from an array of a = [1,2,3,4]. the logic is a.slice(a.lentgh - 2)
    return keccak256HashByteArray.slice(keccak256HashByteArray.length - 20);
}

module.exports = getAddress;

const getAddress = require('../getAddress');
const secp = require('ethereum-cryptography/secp256k1');
const { assert } = require('chai');
const { toHex } = require('ethereum-cryptography/utils');

const PRIVATE_KEY =
    '6b911fd37cdf5c81d4c0adb1ab7fa822ed253ab0ad9aa18d77257c88b29b718e';
const EXPECTED_ADDRESS = '16bB6031CBF3a12B899aB99D96B64b7bbD719705';

describe('Get Address', () => {
    it('should get the address from a public key', async () => {
        const publicKey = secp.getPublicKey(PRIVATE_KEY);

        const address = toHex(getAddress(publicKey));

        assert.equal(address.toLowerCase(), EXPECTED_ADDRESS.toLowerCase());
    });
});

Application of ECDSA in SSL/TLS

SSL/TLS (Secure Sockets Layer/Transport Layer Security) is a protocol used to secure website connections and protect sensitive data transmitted over the internet. ECDSA (Elliptic Curve Digital Signature Algorithm) is an important component of SSL/TLS that helps establish the authenticity and integrity of the communication.

When you connect to a secure website (HTTPS), your web browser and the server engage in a handshake process to establish a secure connection. This handshake involves the use of public-key cryptography, and ECDSA is used specifically for generating and verifying digital signatures.

Here's a simplified explanation of how ECDSA works in this context:

1. Key Generation:

   • The server generates a pair of cryptographic keys: a private key and a corresponding public key. These keys are mathematically related but computationally difficult to reverse-engineer.

2. Certificate:

   • The server's public key is combined with additional information, such as the website's domain name, and bundled into a digital certificate. This certificate is signed by a trusted third-party organization called a Certificate Authority (CA).

3. Handshake:

   • When you visit a secure website, the server presents its digital certificate to your browser during the handshake process.
   • Your browser verifies the authenticity of the certificate by checking its digital signature, which is generated using ECDSA.
   • The signature is decrypted using the CA's public key, which is pre-installed in your browser as a trusted authority.

4. Secure Communication:

   • Once the certificate is validated, your browser generates a random symmetric encryption key for the session. This key is used to encrypt and decrypt the data transmitted between your browser and the server.
   • The server's public key, obtained from the certificate, is used to encrypt the symmetric encryption key before sending it securely to the server.. NOTE: you see how the the symmetric key is securely transmitted using, public key cryptography. Basically, we’re encrypting the key using servers public key so only server can get access to the key.

You may feel dumb and ask this question again in future: Okay thanks, but in step 4 (Secure communication), you said " a random symmetric encryption key for the session. This key is used to encrypt and decrypt the data transmitted between your browser and the server." if this key is symmetric this means that the server will also have access to it right? So, how does the server know this key when it is generated on browser? It’s already answered in step 4 but here is more detailed explanation.

You’re correct that a symmetric encryption key means that both the browser and the server have access to it. Allow me to clarify the process of how the symmetric encryption key is securely shared between the browser and the server.

In step 4 of the handshake process, when the browser generates a random symmetric encryption key, it doesn’t directly send this key to the server. Instead, it uses the server’s public key, obtained from the server’s digital certificate, to encrypt the symmetric encryption key.

Here’s a more detailed explanation of the process:

The browser generates a random symmetric encryption key, which is typically a strong and secure key for the encryption algorithm being used (such as AES).

The browser then uses the server’s public key (obtained from the server’s digital certificate) to encrypt the symmetric encryption key. This step ensures that only the server, with its corresponding private key, can decrypt the symmetric encryption key.

The encrypted symmetric encryption key is sent to the server.

Upon receiving the encrypted symmetric encryption key, the server uses its private key to decrypt it, recovering the original symmetric encryption key.

At this point, both the browser and the server possess the same symmetric encryption key, which is used for encrypting and decrypting the data transmitted during the secure communication session.

So, while the symmetric encryption key is generated on the browser side, it is securely transmitted to the server using the server’s public key for encryption. This ensures that only the server can decrypt and access the symmetric key, maintaining the confidentiality of the key during the handshake process.

To summarize, ECDSA is used in SSL/TLS to ensure the authenticity and integrity of the server’s digital certificate during the handshake process. It helps establish a secure connection and enables encrypted communication between your browser and the server, protecting your data from unauthorized access or tampering.

I asked this question, why is the symmetric encryption key is needed?

Why is a symmetric encryption key needed in SSL/TLS? Couldn't we just use the server's public key and the browser's public key? Wait does the browser even has a public key? Maybe I am dumb? lol

Answer:

No need to worry; it’s not a dumb question at all! Let’s clear up the confusion.

In SSL/TLS, symmetric encryption is used for efficient and secure communication between the browser and the server. While public key cryptography (asymmetric encryption) plays a vital role in the initial handshake and key exchange process, it is not practical for encrypting the entire data stream.

Here’s why a symmetric encryption key is needed:

1. Efficiency: Symmetric encryption algorithms are much faster than their asymmetric counterparts. They are designed to encrypt and decrypt data quickly, making them more suitable for encrypting large amounts of data in real-time.

2. Performance: SSL/TLS is used for secure web communication, where both the browser and server need to encrypt and decrypt data during the session. By using symmetric encryption, which requires less computational overhead, the performance of the communication is significantly improved.

3. Shared Key: Symmetric encryption requires a shared secret key between the browser and the server. This shared key ensures that both parties can encrypt and decrypt the data using the same key. The server and browser do not directly share this key; instead, it is securely exchanged during the handshake process using asymmetric encryption.

Regarding the browser's public key, typically, SSL/TLS does not involve the browser having its own public key. Instead, the browser is responsible for verifying the server's digital certificate and ensuring that it is issued by a trusted certificate authority.

In summary, while public key cryptography (asymmetric encryption) is used during the handshake process to establish a secure channel and securely exchange a symmetric encryption key, symmetric encryption is employed for actual data transmission due to its efficiency and performance advantages.

ECDSA vs RSA ( really amazing article here by cloud flare https://blog.cloudflare.com/ecdsa-the-digital-signature-algorithm-of-a-better-internet/)

Why is ECDSA the algorithm of choice for new protocols when RSA is available and has been the gold standard for asymmetric cryptography since 1977? It boils down to the fact that we are better at breaking RSA than we are at breaking ECC.

As we described in a previous blog post, the security of a key depends on its size and its algorithm. Some algorithms are easier to break than others and require larger keys for the same level of security. Breaking an RSA key requires you to factor a large number. We are pretty good at factoring large numbers and getting better all the time. Breaking an ECDSA key requires you to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP). The mathematical community has not made any major progress in improving algorithms to solve this problem since is was independently introduced by Koblitz and Miller in 1985.

This means that with ECDSA you can get the same level of security as RSA but with smaller keys. Smaller keys are better than larger keys for several reasons. Smaller keys have faster algorithms for generating signatures because the math involves smaller numbers. Smaller public keys mean smaller certificates and less data to pass around to establish a TLS connection. This means quicker connections and faster loading times on websites.

According to the ECRYPT II recommendations on key length, a 256-bit elliptic curve key provides as much protection as a 3,248-bit asymmetric key. Typical RSA keys in website certificates are 2048-bits. If we compare the portion of the TLS handshake that happens on the server for 256-bit ECDSA keys against the cryptographically much weaker 2048-bit RSA keys we get the following:

                        `sign/s`

256 bit ecdsa (nistp256) 9516.8
rsa 2048 bits 1001.8

(openssl 1.0.2 beta on x86_64 with enable-ec_nistp_64_gcc_128)
That table shows the number of ECDSA and RSA signatures possible per second. On our servers, using an ECDSA certificate reduces the cost of the private key operation by a factor of 9.5x, saving a lot of CPU cycles.

Danger Zone?

We can be relatively confident about the mathematical security of ECDSA (save for some questions about the choice of curve(https://safecurves.cr.yp.to/)). The history of cryptography shows us that good cryptography has been repeatedly defeated not because of bad math, but because of bad implementations of good math.

One interesting quirk of the ECDSA algorithm is that every signature requires some random or unpredictable data as input. If the source of randomness is predictable to an attacker, then they can figure out the private key. Hackers have exploited this vulnerability in several high-profile incidents.

In 2010, a flaw in the way random numbers were used in ECDSA on Sony’s Playstation 3 resulted in a private key being leaked. More recently, some Android devices were found to be incorrectly generating random values, resulting in a massive theft of Bitcoins from devices running Bitcoin software.