DEV Community: Aditya Kumar Singh

Overview of Symmetric Key Cryptography

Aditya Kumar Singh — Sat, 29 Oct 2022 05:44:14 +0000

Today we usually use the word crypto in our daily conversations as short for cryptocurrency. The popularity of crypto, at least in public opinion, has completely overshadowed the underlying principles that cryptocurrency works upon. Cryptocurrency and various other applications - NFTs and DAOs are based on a single and the most fantastic technology of today - Blockchain.
Well, Blockchain is a technology and similar to other technologies, there is not one, not two, but many techniques and principles used from the book of science and mathematics for perfecting this technology, which still is not perfect and scalable to the scale we need it to be. However, Blockchain uses "Public-Key Cryptography", specifically Elliptical Curve Cryptography (ECC), for the identification and authentication of senders and messages. This article will only provide an overview of Symmetric Key Cryptography. The upcoming articles of this series will cover the various public-key cryptography techniques and possibly the underlying mathematics behind them.

The meaning of the word Cryptography

Today the words "cryptography", "cryptology", and "cryptanalysis" are commonly interchanged. However, they have slightly different meanings. "Crypt" means hidden, and "graphy" means writing in Greek. So, cryptography means hidden writing. Typically when a cypher is constructed, the idea is that there is a person or a group who will "legitimately" decipher the text. In order to legitimately decipher, it is understood that the person will have access to what's referred to as a "key". Simply put, a "key" is any means of quickly and efficiently determining the original text. A good cypher system is constructed so that deciphering the text without the correct "key" is almost impossible.
Cryptanalysis refers to the analysis of hidden texts - cypher texts without having access to a legitimate "key" to break the cypher. Cryptology means the study of hidden writings or secrets. This encompasses both the establishment of encryption methods and analysis of a cypher in order to break it without the associated key.

Symmetric Key Cryptography

The hiding of secrets in written and pictorial form to communicate information crucial to war strategies or even for simple games dates back thousands of years, going far back in time to ancient Egypt. These people used the type of cryptographic systems that incorporated "Symmetric Key Cryptography".
Symmetric key systems are cryptographic systems in which decrypting is as simple as reversing the encryption used. The sender encrypts the plain text with a key, and this encrypted text - cypher text is communicated over an insecure channel, and the receiver decrypts the cypher text using the exact same key. A trivial example of this kind is "Caesar Cypher", which comes under the family of "substitution cyphers". The letters in the plain text are replaced by some other letters of the same alphabet in a fixed pattern that both the sender(obviously) and receiver are aware of.

The simplicity of using the same key both to encrypt and decrypt is offset by the difficulty of ensuring that all parties involved have the needed keys in a tense situation and also when people may be widely dispersed geographically. The lack of an ideally secure channel in such environments for exchanging keys is the deal-breaker for symmetric key cryptography. People have tried their way around it by using "code books" in the 1800s, which listed which keys to be used on which dates of the month. The sender and the receiver both needed a copy of the same "code book" for this. However, if the "code book" gets compromised, the communication over the entire duration would be leaked, which would most likely lead to devastating consequences.

Confusion and Diffusion

Claude Shannon was one of the first to formalize the principal aims of a cryptographic system. He argued that a cryptosystem designer should assume that the system may be attacked by anyone who has access to it., as was indeed the case during the two world wars when machines were stolen and reverse engineered. He argued that the only point of secrecy should be the key, but that the system design should complement the security by incorporating the "confusion" and "diffusion". Confusion is intended to make the relationship between the key and the cypher text as complex as possible. Diffusion refers to rearranging or spreading out the bits in the message so that any redundancy in the plaintext is spread out over the cipher text so that the complexity for recognizing patterns in cypher text is increased multifold.

The Enigma

Enigma Encryption Machine - Mechanical Cypher MachineEnigma machine designed by Arthur Scherbius and used by Germans during WWII utilized a symmetric key encryption technique. In this case, the "key" was the setup configuration of the machine, including the rotors utilized, the rotor order, the ring setting of each rotor, the starting position of each rotor, and the plugboard letter swaps on the front panel.
Both the sender and receiver needed to have the exact setup configuration of the machines to communicate. At the start of every month, a list of that month's day keys were distributed. This is an example of the "code books" technique in symmetric key cryptography.

For extra security, after an Enigma operator set up his machine with the day key. He would then choose to rotate the position of each rotor to some random position called the Grundstellung or indicator-setting. This information was communicated to the receiver unencrypted. The sender would then select a new series of random letters to encrypt and type them into the Enigma twice consecutively. After entering this information, the sender would rotate the rotors once again to the position of the random letters previously chosen and entered. The sender now proceeds to encrypt the message.

The receiver would have the Enigma set with the day key settings. He would then receive the Grundstellung unencrypted from the sender and change the Enigma configuration accordingly. Next, the initial two consecutive series of encrypted random letters would be entered, revealing the rotor position settings to be set to decrypt the remaining message.

Hope you learnt something new and interesting. If you find cryptography and Blockchain exciting, follow me because I will be coming up with more on this.

Adios 😊!

Public Key Cryptography

Aditya Kumar Singh — Sat, 29 Oct 2022 05:37:20 +0000

In my previous article, I discuss an overview of symmetric key cryptographic systems. The major drawback of such a system that held symmetric key cryptography to be used widely in business circles was the exchange of keys over an insecure channel. In the absence of any other method of secure information exchange, governments established methods of managing keys. However, many in the business world were not interested in employing circumspect and perhaps even dangerous methods of key exchanging keys. In the 1960s, this became known as the "key management" problem.

Diffie - Hellman Key exchange

In 1976, Whit Diffie and Martin Hellman published a paper describing a method of establishing a common key securely over an insecure channel which used exponentiation and the fact that exponents can be multiplied in any order with the same results. The protocol (steps) set out here permits two parties (say Alice and Bob) to use these insecure channels to exchange information in such a way that after several communications, they share a single value known only to them and then use this key to further conceal communications.

Step 1: In the first step, Alice and Bob agree on common parameters which do not have to be kept secret from anyone else. These are

a large prime number q and
a primitive root a(mod q)

Now both (we take Alice here) generate their own public key independently by

choosing a secret integer: XA < q
and computing their public key: YA = a^xA (mod q)

Alice and Bob now publish their respective public keys YA and YB wherever they like. In particular, they need to know each other's public keys and can simply send them to each other directly.

Step 2: Alice and Bob now establish a common value as follows:

Bob computes YA^XB (mod q) using his private key;
Alice computes YB^XA (mod q) using her private key;
But both are the same: KAB = a^XAXB (mod q).

Note: Each party uses their own secret key in generating a common value, so no one else is able to do this. Consequently, K AB is known only to A and to B and can now be used as a key in encryption between Alice and Bob.

However, this scheme was only useful for establishing keys and did not actually encrypt any data. The search was still on for an encryption scheme that allowed anyone to send an enciphered message to any other person without pre-establishing keys, such that only the targeted recipient could decrypt the message.

The first example of such a solution appears to have been developed independently from two sources.

Basically, the idea is for each person to have two keys, one to encrypt and one to decrypt. The two keys would have to be bound together in some fundamental way in order for them to "invert" each other, but it should be impossible for an attacker to derive one from the other. The encryption key would be published as we publish our phone number. However, only the recipient would know his/her decryption key; it would not be revealed to anyone else. This idea completely solved the problem of exchanging keys, except for the fact that initially, no one had a real way of setting up such a scheme.

RSA (Rivest-Shamir-Adleman)

In 1978, the first actual method for implementing such a scheme was published by Ronald Rivest and is now widely known by the first letter of each of the authors' names as RSA. The security of RSA was based on the difficulty of factoring large integers. In 1977, it was finally revealed that members of the British intelligence agency Government Communications Headquarters (GCHQ) had also invented essentially the same scheme early in the 1970s. A detailed description of the RSA scheme will be discussed in later articles.

ElGamal

The ElGamal cryptographic algorithm was invented a few years after the RSA scheme, developing from the PhD thesis of Taher ElGamal, which was awarded in 1984. The underlying security principle on which this scheme is based is quite different from RSA. In ElGamal, the target is to determine the exponent in an equation of the form \(a = b^x\) where a and b are known. A detailed description of the ElGamal scheme will be discussed in later articles.

Elliptical Curve Cryptography (ECC) is another public key encryption algorithm which is reported to be 50 to 100 times faster than RSA on 256-bit security levels.

A Comparison of Symmetric and Asymmetric Key Cryptography

All known asymmetric(public) key schemes are far more computationally expensive than symmetric key schemes. For example, the disadvantage of the ElGamal scheme is that the encrypted message becomes very big, about twice the size of the original message. Similarly, RSA is a lot slower than DES which is a symmetric key protocol, almost by a factor of 1000. For this reason, public key schemes are traditionally used only for small messages, such as secret keys, whereas symmetric key schemes are retained for sending large messages.

Both symmetric and asymmetric key schemes use encryption and decryption keys, but in symmetric key schemes, both of these are identical. In contrast, they are different but related in the asymmetric (public) key system. However, the security of such a system is based on the difficulty of deriving one from another.

Cryptography - More than Just Hiding Secrets

As the adoption of computers and the internet increased for communication, various applications of cryptographical schemes other than just concealing information were developed to address the needs of the digital age.

Q. How to confirm that a message received indeed came from the sender purported? (It's quite easy to change the name of the sender in most e-mail systems).

Q. How to prevent a sender from claiming that they did not, in fact, send the message you received?

Q. How to ensure that the message received was the one sent and had not been altered?

The most recent significant application of cryptography is, therefore, for the identification of senders, authentication of senders and recipients, as well as the message themselves, and digital signatures applied to messages.

Digital Signatures for User Authentication

A digital signature is a method of applying data to a message which identifies the sender of the message in the same way that a written signature on a piece of paper confirms authorship. All known public key schemes can be used to implement this in practice.

In using a public key scheme to send a signed message to Bob, Alice can simply encrypt the message using her private key. When Bob receives the message, he can verify that it was "signed" by Alice by applying Alice's public key to the received encrypted message. The result should be a readable message that makes sense to Bob. If it was not signed with Alice's private key, then applying her public key to decrypt the message would result in nonsense, so Bob can be sure that it was signed by Alice.

Message Authentication

Hashing algorithms, along with encryption schemes, can be used to verify the message and if it has been altered from its original version during the transmission to the recipient. The original message M can be hashed (more on hashing algorithms in later articles), and the generated digest of the message D can be appended to the message M||D. This appended string is then encrypted using the public key of the recipient and the private key of the sender in any order. The recipient, on receiving this doubly encrypted string M||D, can perform double decryption once using his private key and once using the sender's public key in a pre-determined order. He can then separate the message M and digest D using many methods (like the first few bits can be used to depict the length of the message M). He can independently calculate the message digest D' and compare D and D' to verify if the message has been altered from its original version.

That was about public key cryptography from my side. If you want to read about symmetric key cryptography, you can refer to my this article.

Adios 👋

What do we mean by UTXOs?

Aditya Kumar Singh — Sun, 18 Sep 2022 12:42:37 +0000

Anyone learning Blockchain Technology will be puzzled by the concept of UTXOs and how they enable blockchain protocols (specifically Bitcoin protocol) to make transactions.

I will be talking about Bitcoin, which uses the UTXO model to keep track of transactions and detect double-spending. Ethereum uses the Account/Balance Model for keeping track of the balance of a particular account. UTXO stands for Unspent Transaction Output. UTXO is of two types:

Input UTXO
Output UTXO

In bitcoin, the funds in a transaction are treated as a single unit, and to spend the funds received from a transaction, you have to spend the entire fund referenced in that input transaction. If you only want to spend only a fraction of the bitcoin in that referenced by that input transaction, then you need to create two transactions, one to the potential receiver’s account and another to your account.

Input UTXOs are basically the transactions whose funds have not been spent, i.e. not yet referenced as an input to any other transaction.

Output UTXO are the transactions which are generated after a transaction becomes successful.

Understanding Transactions in UTXO model

Consider these bitcoin transactions, which result in transferring a sum of 0.61 BTC to my account.
Now I want to buy a truck that costs 0.55 BTC.
Now, to spend 0.55 BTC, I have to reference one or more transactions called input transactions whose cumulative sum is equal to or more than 0.55 BTC.
If I have an option to choose from those transactions shown above (let’s suppose all other transactions referencing my account are either output transactions — where I am sender), then I have only one option for a set of input transactions, i.e. first and second transactions.
But hey, these transactions result in 0.6 BTC, then where is the remaining 0.05 BTC going after I pay for 0.55 BTC? These remaining amounts can be used in these three ways: -

Send the remaining amount back to your account.
Use the remaining amount as the transaction fee. Every transaction on the blockchain has associated transaction fees.
Send the remaining amount to someone else.

6.. After the transaction is confirmed, the transactions in my account will look like this:

7.. The first two transactions that have now been spent can’t be referenced as input UTXOs to any other transactions.

8.. The transaction in purple is the outgoing transaction (BTC is sent and not received), so it also can’t be used as input UTXO in any transaction.

9.. The 3rd and the 5th transaction shown in green are the transactions which are unspent and can be used as input UTXO to other transactions.

That’s about it for now.

Adios 👋

Basic Operations in Bitcoin Blockchain

Aditya Kumar Singh — Sun, 28 Aug 2022 17:59:00 +0000

We have all heard about Blockchain and how it solves many security and counter-party risks, being a decentralised and immutable digital ledger. This article mainly focuses on how the Bitcoin Blockchain (mother of all blockchains) implements these security measures and removes the need of a centralised intermediary for the transfer of value.

The main operations in a blockchain are transaction validation and block creation with the consensus of the participants. However, there are many underlying operations which help bitcoin solve the problem of double spending.

Operations in the decentralised network are the responsibility of the peer participants and their respective computational nodes. These computational nodes can be a laptop, desktops, or server racks. These operations include validation transactions, gathering the transactions for a block, broadcasting the ballot transactions in the block, consensus on the next block creation, and chaining the blocks to form an immutable record.

Basic Operation by a Node(Miner)

Validation of Transactions - A Blockchain validator performs validation by verifying whether transactions are legal (i.e. not malicious or double spends etc). This process involves validating more than 20 criteria, including size, syntax, etc., some of these criteria are - Referenced Input and Unspent Transaction Output(UTXOs) are valid, reference input amount and output amount matched sufficiently. All the valid transactions are added to a pool of transactions - called mempool
Gathering(grouping) Transactions - Collecting transactions for a block. This grouping of transactions is done at an individual level. All the miners can independently group whatever transaction they want to choose for their candidate block. However, the miner's fees are the sum of all the transaction fees + block rewards using a coinbase transaction.
Broadcasting valid transactions & blocks - Once the miner has solved the mathematical puzzle, it broadcasts his selected block with the puzzle solution.
Consensus on next block creation - The broadcasted block is then verified by all nodes at individual level.

It may happen that two nodes transmit their blocks for the same block number after solving the mathematical puzzle. In that case every node will start working on top of the block which reached it first, and this results in the forking of blockchain. The forking of the chains usually completely resolves in 5-6 further blocks. Blockchain resolves this forking of chains by following a rule : **Largest chain is the most true version of the truth* and the largest chain is accepted by the nodes at individual level every time there is an ambiguity.*

Chaining Blocks - Once the block is selected, block is added to the local copy of blockchain at node level.

Bonus

The algorithm for consensus is called proof-of-work protocol since it involves work i.e. computational power to solve the puzzle and to claim the right to form the next block.
Transaction zero, index zero of the confirmed block is created by the block's miner. It has a special UTXO and does not have any input UTXO. It is called the coinbase transaction that generates a minor's fees for the block creation.

To summarise, the main operations in a blockchain are transaction validation and block creation with the consensus of the participants.
There are many underlying implicit operations as well in the bitcoin blockchain.
For more fine-grained details you can refer to this article.