4
$\begingroup$

I've been baffled by all the different kinds of names which are given to cryptographic algorithms.

There are block ciphers and stream ciphers (AES and RC4).

There is symmetric and asymmetric encryption (AES and RSA).

I get that block ciphers and stream ciphers are symmetric encryption, but Wikipedia makes things more difficult because it states it's the other way around:

By type of key used ciphers are divided into:

symmetric key algorithms (Private-key cryptography), where the same key is used for encryption and decryption, and asymmetric key algorithms (Public-key cryptography), where two different keys are used for encryption and decryption.

then it goes on to say:

Ciphers can be distinguished into two types by the type of input data:

block ciphers, which encrypt block of data of fixed size, and stream ciphers, which encrypt continuous streams of data

However, RSA is not a cipher because it is not a block cipher nor a stream cipher, is it?

So am I missing something, or is there indeed a gap in this terminology?

$\endgroup$
  • 1
    $\begingroup$ This is a bit opinion-based. I would apply the term "cipher" only to symmetric-key encryption algorithms; hence RSA is indeed not a cipher. $\endgroup$ – yyyyyyy Mar 11 '15 at 14:25
  • $\begingroup$ Yes of course, Crypto is a very very young science. but be still patient for a few decades more before seeing the emergence of an unified theory in that field. $\endgroup$ – Robert NACIRI Mar 11 '15 at 15:56
  • $\begingroup$ I would define "cipher" as a cryptographic algorithm that encodes data through use of a key, and that would include asymmetric algorithms which use a different key to decrypt. $\endgroup$ – Richie Frame Mar 13 '15 at 9:39
9
$\begingroup$

It sounds like you're basically asking for a definition of the word "cipher". I agree that it's somewhat fuzzy and complicated — that's mainly because "cipher", on its own, is not a precisely defined technical term in modern cryptography, but a descriptive word whose meaning, like that of most other English words, has evolved gradually over time.

So, let's start from the beginning.

The word "cipher", as any good dictionary can tell you, originally comes from the Arabic word ṣifr (صفر), meaning "empty" or "nothing", and also the numeral zero. As the Arabic numerals (notable, compared to the older Roman numerals, for their inclusion of a symbol for zero) were introduced to Europe, this word was adopted into Medieval Latin as cifra, whose meaning broadened to cover any of the Arabic number signs, or even any other strange sign or symbol. (These senses are still retained e.g. in the French word chiffre, whose meanings include "numeric digit", "figure" and "cipher".)

It's not fully clear how the word used for Arabic digits came to be also applied to any kind of secret or obscured writing system, but given that the new number system was only adopted gradually, and long remained, in the public view, a strange and incomprehensible notation only used by a few learned men and secretive merchants (who, being also generally interested in confidentially recording and discussing matters financial and political, were also early adopters of cryptography), it is perhaps not surprising.

In any case, by the 19th and early 20th centuries, during the peak days of the "classical cryptography" era, before the introduction of computers and modern cryptographic theory, methods of transmitting encrypted messages had come to be generally divided into two broad categories: "codes", which replaced words or entire phrases with specific agreed-upon symbols (often distributed in "code books"), and "ciphers", which were based on replacing and/or rearranging individual letters in a message. While codes were generally regarded as more secure (since a good code offered fewer opportunities for a cryptanalyst to find patterns in the message), ciphers had the definite advantage of being able to encrypt any messages, even ones that the compiler of the code book had not anticipated.

The ciphers used in the classical era were, in turn, grouped into several distinct types, such as:

  • substitution ciphers, which worked by transliterating the message into a secret alphabet; and

  • transposition ciphers, which instead used the normal alphabet, but shuffled the letters of the message into a seemingly random order according to some prearranged pattern.

Of course, an advanced cipher might combine both of these types, and there were even systems, like the French Great Cipher, which combined elements of ciphers and codes. Also, while the simplest substitution ciphers used just a single fixed secret alphabet, more advanced schemes — like Bellaso's chiffre indéchiffrable, commonly misattributed to Blaise de Vigenère, or the later rotor machine ciphers of the 20th century — used a different alphabet for each letter of the message, making them considerably harder to break.

The electromechnical rotor machine ciphers, such as the famous German WWII Enigma machine, were the state of the art for much of the early and mid-1900s, during the transition period from classical to modern cryptography. They (like the older polyalphabetic substitution ciphers of Bellaso, Vigenère and others) may be seen as early examples of stream ciphers, although the term "stream cipher" did not really enter the common vocabulary before the 1970s:

    Graph of the relative frequencies of the terms "stream cipher", "block cipher", "substitution cipher" and "transposition cipher"
Graph of the relative frequencies of the terms "stream cipher", "block cipher", "substitution cipher" and "transposition cipher" between the years 1900 and 2000, generated using Google Ngram Viewer.

What happened in the 1970s was the invention of a new kind of cryptographic tool — the block cipher, developed in its modern form by Horst Feistel at IBM, who designed the Lucifer cipher that eventually became DES. (Of course, the idea was not entirely without precedent: the Hill cipher, from 1929, had also operated on blocks of characters, as did the various earlier polygraphic substitution ciphers, and of course much of the general theory had been introduced by Claude Shannon in 1949. Still, in many ways, Lucifer and DES did represent a strong and radical departure from earlier traditions in civilian cryptography.)

The thing about block ciphers is that, unlike stream ciphers (a term which, in its broadest sense, covers pretty much every practical encryption system capable of encrypting arbitrarily long messages), a block cipher is not really very useful on its own: it's great if you just happen to need to encrypt blocks of, say, 64 or 128 bits into other blocks of the same length, but how often is that the case?

To make a block cipher practically useful, you will need to combined it with some kind of a higher-level scheme (often called a mode of operation) to turn it into a more general-purpose encryption scheme (which will, usually, be some kind of a stream cipher, in the broad sense). Thus, a block cipher is perhaps better regarded as a useful tool for building ciphers (and other cryptographic schemes), rather than as a general-purpose cipher in itself.

So why apply the name "cipher" to them at all, then? Well, for one thing, that's the name the folks at IBM and NBS (now NIST) chose to use back in the 1970s, and the rest of the world simply followed their lead. From a historical perspective, it's also a fairly understandable decision: in cryptographical parlance of the day, a "cipher" was something used to encrypt data, and that's certainly what DES did, if in a somewhat unconventional manner. Thus, it made perfect sense at the time to call it a "cipher", but specifically a "block cipher", to differentiate it from other types of ciphers used at the time.

However, the end result of all this is that, today, we have two different kinds of "ciphers" used in modern cryptography: stream ciphers, which are used to encrypt (streams of) data, and block ciphers, which are (mostly) used to build other kinds of cryptographic algorithms (including stream ciphers).


What about asymmetric encryption schemes like RSA, then?

Well, they're certainly ciphers in the broad sense of "something used to encrypt data", and indeed several authors do use terms like "public-key cipher"or "asymmetric cipher".

On the other hand, if block ciphers are somewhat restricted in their direct applications, public-key algorithms like RSA are even more so. For one thing, a block cipher can encrypt any string of 64 or 128 bits; RSA can encrypt a number between 0 and the recipient's RSA modulus (minus one). This may not seem like much of the difference (since it's easy enough to map bitstrings to numbers and back), but do consider the fact that this means that the space directly encryptable messages is different for each RSA key.

Also, "textbook RSA" is only secure if the messages are unpredictable, more or less uniformly distributed between 0 and the modulus, and if the same message is never encrypted with multiple RSA keys. If the messages belong to a small subset of the full range, an attacker can easily decrypt them by a brute force attack; if they're too small compared to the modulus, or if the same message is encrypted with too many keys, they may be able to break the encryption much more easily than by brute force.

Also, even if those problems are fixed by appropriate padding (effectively adding enough (pseudo)random bits to the messages to make them unique, unpredictable and long enough), RSA (like most asymmetric encryption schemes) is still poorly suited for directly encrypting long messages. Thus, the standard way of using RSA is a part of a hybrid encryption scheme, where the data is first encrypted using a symmetric encryption scheme (i.e. a stream cipher, broadly speaking) with a random key, and that random key is then encrypted with RSA.

All these issues make some cryptographers (including myself, to some extent) reluctant to call RSA a "cipher", in the same sense as the term is applied to modern stream ciphers and earlier classical substitution / transposition ciphers. In these people's minds, a "cipher" is something you could use to encrypt a normal plaintext message (and not just a random number in some interval) directly, whereas RSA would be better described as just an "algorithm" (in its "textbook" form, which is not really secure on its own) or a "cryptosystem" (with all the additional trappings needed to turn it into a secure and usable encryption scheme).

(Ps. It's worth noting that there's quite a bit of variation between different public-key encryption schemes, in terms of what they can encrypt directly. For example, traditional ElGamal encryption is pretty flexible, and can safely encrypt any number less than the (fixed) order of the group, which may be, and usually is, shared by all recipients. Conversely, for most elliptic curve based systems, even just efficiently and unambiguously encoding an arbitrary message as an encryptable curve point is a non-trivial exercise.)

$\endgroup$
  • $\begingroup$ Great answers, really detailed and +1 for starting with the origins :) $\endgroup$ – Vincent Mar 12 '15 at 7:36
4
$\begingroup$

First, be careful with Wikipedia. The more specialised you get, the more poorly written articles there are. You should prefer material which has been written by experts, such as textbooks or online lecture notes.

As yyyyyyy says in the comments, this is probably opinion-based, and most people probably don't care. I can only find one book which uses the word "cipher" in the context of asymmetric encryption (namely, the book of Hoffstein, Pipher and Silverman, which sometimes speaks of "asymmetric ciphers"). Derivative words such as "ciphertext" are commonly used in both symmetric and asymetric encryption, however.

$\endgroup$
  • $\begingroup$ Ye i know but for descriptions i do often use wikipedia, more imporant information i do try to get from different sources. is there a distinction for asymmetric encryption like there is for asymmetric encryption? $\endgroup$ – Vincent Mar 11 '15 at 14:37
  • $\begingroup$ Do you mean something similar to the distinction between block and stream ciphers? I don't think there is any, but there are other ways to classify asymmetric encryption algorithms, such as the hard problem they are based on (integer factoring, ff discrete log, ec discrete log, etc.). $\endgroup$ – fkraiem Mar 11 '15 at 14:41
  • 1
    $\begingroup$ From a practical point of view, asymmetric cryptosystems can be seen as block ciphers (and e.g. BouncyCastle does label them that way), because you have an input and an output of fixed length, which are usually the same. So you could theoretically use some mode of operation like CBC, and use RSA encryption / decryption. Performance will be horrible tho... when talking about asymmetric encryption, people usually think implicitly about messages, which fit within the structure. If your real message is longer, use hybrid encryption. $\endgroup$ – tylo Mar 11 '15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.