CommonLounge Archive

Cryptosystems and their Components, Design Objectives and Basis for Security

January 17, 2018

A cryptosystem is a pair of algorithms: one for the encryption of data and another for decryption. Often these algorithms use a unique key which should be kept secret, in which case the process for generating and sharing the key is also considered part of the cryptosystem.

Modern cryptography is essential to the digital world we live in and has grown to be quite complex. It is used for sending messages in a secure manner on the internet, such as our credit card information and other private data. Encryption is used to keep our data secure online and locally. The Advanced Encryption Standard (AES) is used by governments to maintain the secrecy of their documents and was chosen from a number of candidates across the mathematics community for its security and efficiency.

In addition, digital security can also be used to maintain anonymity, to authenticate one’s identity via digital signatures, to demonstrate proof of work in blockchain technologies and to ensure that software and messages are free from tampering.

Definitions

Cryptography terms

Here are a few definitions of some terms relating to cryptography and cryptosystems:

  • Plaintext: The original message in its original legible form.
  • Ciphertext: Encrypted text that will appear to be a random string.
  • Encryption: The process of converting data into its cryptic form that prevents unauthorized access, i.e. converting plaintext to ciphertext. This process requires encryption keys which provide information regarding the specific implementation of a given encryption algorithm.
  • Decryption: The process of converting encrypted data back into its original form for use, i.e. converting ciphertext back to plaintext. Decryption requires a decryption key which provides the specific information required to ‘undo’ the encryption.
  • Symmetric Key Cryptosystems: Cryptosystems that use the same key for encryption as well as decryption. This key is assumed to be a shared secret between the two parties exchanging messages. A few examples of Symmetric Key Cryptosystems:
  • Cipher: A system of encryption that maps each character to a substitute.
  • Code: A system of encryption that maps each word or feature to a substitute.
  • Shift Cipher: A cipher that replaces each character with another chosen by moving forwards through the alphabet by some fixed shift factor.
  • Asymmetric or Public Key Cryptosystems: Cryptosystems that use public-private key pairs. This enables anyone to encrypt messages for sending to the publisher of the keys (using the public key) but only the holder of the private key will be able to decrypt the messages.
  • Digital Signatures: A digital code (generated and authenticated by public key encryption) which is attached to an electronically transmitted document to verify its contents and the sender’s identity.

Number theory terms

The following are some important concepts required for cryptography from the field of number theory

  • Modulo: The remainder operator (e.g. 17 modulo 5 is 2, i.e. 17 when divided by 5 leaves a remainder of 2). This is often shortened to mod, we write 17 ≡ 2 (mod 5), read as “17 is congruent to 2, modulo 5”.
  • Coprime: In number theory two values are said to be coprime or relatively prime if they do not share any common prime factors. That’s to say that their greatest common divisor (GCD) or highest common factor is 1.

Characters

It is general practice in cryptography to follow the standards of Rivest, Shamir and Adleman, the inventors of the RSA encryption algorithm, by using Alice and Bob as the main protagonists in any example of cryptosystem protocols. In examples of attacks, Eve is usually cast as the attacker. That is, Alice wants to send messages privately to Bob, and Eve is trying to spy on the messages.

Design Objectives & Goals

The design objectives of a cryptosystem can be summarized by Kerckhoff’s Priniciple:

The system must be secure even if everything except the private key is public information. In particular, the design of the system must not be required to be kept secret.

This is the approach taken by modern cryptography (as compared to earlier cryptographic systems, which often relied on obscurity, i.e. aiming for security by keeping the system or parts of it secret or unclear.)

Beyond security computational efficiency and the practicality of implementation are sub-objectives in cryptosystem design. This is shown in the development of AES whereby the US Government accepted suggestions for algorithms and 15 made it to the final. Some of the finalists were more secure than the ultimate winner but were dismissed for requiring too much processing power.

The trade-off between complexity and therefore security and ease of implementation can be further seen in the guidance for the use of AES encryption. Top secret information is encrypted using a 192 or 256 bit key whereas less highly classified information may be encrypted using a 128-bit key for efficiency. AES involves 10 rounds of encryption processes for 128-bit keys, 12 rounds for 192-bit keys and 14 rounds for 256-bit keys.

Symmetric vs Asymmetric Cryptosystems

A cryptosystem consists of an encryption algorithm, a decryption algorithm and some secure private key at a minimum. The key may consist of multiple parts and under certain circumstances parts of this key may be made public.

Symmetric Cryptosystem

Diagrammatic representation of a symmetric cryptosystem

Symmetric cryptosystems use the same key for encryption and decryption. Shift cipher is an example of a symmetric cryptosystem since the encryption shifts the alphabet by a given factor which is then reversed for decryption. This shows that the same key is used for encryption and decryption even though the encryption and decryption algorithms are not identical (they are inverses of one another). AES encryption is a more complex example of symmetric encryption. Symmetric cryptosystems are used following secure key exchanges in bilateral communications or in the most frequent case of AES for personal encryption or encryption within an institution where all of the members may carry the encryption (and therefore decryption) key so that they may read the internal documents but they remain protected from external attack.

Asymmetric Cryptosystem or Public-Key Cryptosystem

Diagrammatic representation of an asymmetric or public-key cryptosystem.

Public keys are only possible in the case of asymmetric cryptosystems, which are also hence called public-key cryptosystems. These are cryptosystems where the encryption key differs from the decryption key. This means that the encryption key can be made public so that anyone may encrypt messages and send them to the holder of the decryption key for them and only them to decipher. These public-key or asymmetric cryptosystems scale well since anyone who wishes to receive messages simply needs to publish their public key and reference the encryption system they are using and secure conversations can then begin. Examples of asymmetric cryptosystems include the RSA and ElGamal cryptosystems.

What makes cryptosystems secure: One-way functions

The security of cryptosystems comes from the one-way nature of the encryption function. These are mathematical functions such that it is efficient to calculate the value of the function given an input, but calculating the inverse (i.e. retrieving the input given the output) is computational infeasible or practically impossible. Note that:

  1. We don’t say completely impossible. The inverse can be calculated given infinite computational resources. The objective is to make it expensive enough (say you’d have to wait 1000 years to decrypt a message, or you need computational power of 1 million computers) so that no one would do it.
  2. We also don’t know with mathematical certainty that there is no way to calculate the inverse function quickly, i.e. there is no proof saying that calculating the inverse is computationally infeasible. We rely on the fact that over decades of attempts and efforts from mathematicians, no one has been able to find a method to calculate the inverse quickly.

Taking the example of the ElGamal cryptosystem where encryption is performed by exponentiation modulo a large prime, the encryption is a one-way function because calculating exponents is easy whereas working out the exponent required for a base raised to that power to yield a given value (the discrete log problem) has no known practical solution. The exponent in this case is therefore the encryption key with its inverse being the decryption key.

The Nature of an Attack

An attacker will attempt to attain the decryption key so that they may intercept and read supposedly secure messages. The simplest attack is a brute force or exhaustive search attack whereby each possible decryption key is attempted until the one that works is found. Generally we protect against this in cryptography by working in a system where the set of possible encryption keys is vast, rendering brute force attacks infeasible. This also represents the need for keys to be periodically updated so as to cause any would be brute-force attackers to have to start again.

Computer security is more than just encryption. Most attacks in the modern era come from imprecise implementation of encryption algorithms and from human factors. Mathematical attacks tend to exploit specifics of a use of encryption for example repeated messages, the use of stale keys and even hardware attacks. The most common weakness in cryptosystems is in the human operators who often fail to keep passwords and encryption keys sufficiently complex and secret. Furthermore a failure to maintain up-to-date software can leave opportunities for attack open as attacks are found and thwarted with software updates.

Novel applications

Today encryption affects more and more of day-to-day life as the digitization of assets and systems accelerates. Some novel applications of cryptography have included the development of TOR or The Onion Router which famously allows untraceable internet use for political dissidents, whistle blowers and journalists. The system works by placing layer upon layer of encryption on each packet of information as it bounces around a network of nodes each of which either adds a layer of encryption or removes one depending on the direction of travel and thereby masks the origin and destination of the requests.

Another novel application of cryptography is blockchain technology. This is the technology behind bitcoin and other cryptocurrencies, enabling what is known as decentralized trust, i.e. the ability of a large group of people to agree on a single truth without requiring a central authoritative entity such as a government or a bank. Bitcoin was invented by a cryptography expert in 2008 due to his distrust of the American financial system which had recently caused the 2008 global financial crisis.

Future of Cryptography

The age of artificial intelligence has also led to advances in cryptography in what has been termed antagonistic development of cryptosystems. This occurs where artificially intelligent systems are pitted against each other to maintain a secure communication scheme and they thereby develop their own cryptosystems with no prior knowledge of cryptography in what has been termed an adversarial generative network. Despite this it is still thought that artificial intelligence (namely neural networks) will be unlikely to supersede humans in cryptanalysis any time soon.

Looking to the future, the advent of quantum computing is a concern for cryptographers and anyone using current cryptography for security. This is because the ability of quantum processors to hold multiple notions simultaneously (i.e. a quantum bit at 0 and 1 simultaneously) could lead to brute force attacks becoming viable since systems no longer need to consider each trial in turn, but may consider all possible keys at once.


© 2016-2022. All rights reserved.