3
$\begingroup$

I have been wondering if numeric base conversion has ever found an application in cryptography. By base conversion, an example that is probably familiar is Base64 encoding. This is an example of numeric base conversion, where the value is converted from one base (ASCII) to another (Base64).

However, unlike base-64 encoding, I am curious about the case where both the set of symbols converted from, and the set of symbols converted to, are a permutation of up to 256 elements. One or both of these bases could be kept secret.

From what I have gathered, one of the differences between encoding and encryption seems to be that the latter involves secret material while the former does not.

From what I have been able to research on my own, base conversion by itself, even with secret bases, does not constitute proper encryption. For starters, it possesses low diffusion and can be vulnerable to basic known-plaintext attacks; Incrementing a counter and converting from ASCII to secret base would yield the bytes of the secret base, one by one.

A potential countermeasure would be to encrypt the plaintext first. However, if the data is properly encrypted already it would appear that there's little to be gained by doing the secret encoding business at all.

An interesting feature is that values in arbitrary bases can still have math performed on them without being converted back. This property is called homomorphic encryption elsewhere, but I'm not about to label it as such here as I'm not even sure confidence of the message can be maintained even without such tricks. And the seemingly required countermeasure in the last point would ruin this property.

I've played with the concept off and on for a while, but have never been able to think of a solid use case for the idea. Lately I have been questioning that a use case exists at all, at least as far as crypto is concerned.

I am curious if any crypto systems, failed or otherwise, have attempted to make use of encoding values from one potentially secret base to another. I'm curious about any applications of the idea (to cryptography), and not just those that I explicitly mentioned here.

I have only been able to find mention of a few things:

  • A bunch of pages like this stressing that encoding is not encryption
    • Some emphasizing the difference is because of secret data
  • This page is the closest thing to what I'm looking for that I have found. I disagree with certain assertions contained on the page. To be fair to the author, I did notice the page is over 15 years old.
  • This looked interesting, but literally goes nowhere; It's just a single page overview.

Clarification

By base conversion or encoding, I am referring to changing the meaning of symbols of the given number system as opposed to changing a value represented in it. For example, values in the range 0-255 are normally represented by the symbols/glyphs 0, 1, 2, ...., 255.

The actual value of the string of symbols depends exclusively upon the encoding (number system) used to represent it. '0' only means zero in bases where '0' is the 0th symbol in the base.

So for example, we can choose to interpret the glyph "0" to mean any number 0-255. Then we could interpret the glyph '1' to mean any number 0-255, exclusive of the value indicated by 0 that we assigned previously. '0' only indicates zero in numeric bases where '0' is the 0th glyph.

The process looks like this: value_in_base2 = convert(value_in_base1, base1, base2)

Where value_in_base1 is an ordered collection of symbols whose elements are included in base1, and value2 is an ordered collection of symbols whose elements are included in base2.

Note it is required that base1 contain all symbols used in the original value; It is not required that base2 contain all symbols used in the original value. To clarify why with an example: we can convert an ascii string from ASCII to binary; trying to convert an ascii string from binary to ASCII will not work, as the string contains symbols not found in binary and so cannot be translated.

For some concrete examples: '10' = convert('0000 1010', binary, base_ten) '0A' = convert('0000 1010', binary, hexadecimal) '1111 1110' = convert('0000 0001', binary, inverted_binary) secret_message = convert(message, secret_ascii, secret_base)

The first example converts from binary to base ten. This should make perfect sense. Next, the example converts from binary to hexadecimal. This is standard fare as well.

The third example converts from "regular" binary "01", to inverted binary, "10"; That is, the value 0 is now represented by the symbol '1', and the value '1' is now represented by the symbol '0'.

The last example converts the message as a value in a secret number base to a second secret number base. The values of the output (should) depend exclusively on the bases used in the conversion process; While the secret_message might be presented using the symbols available in the ASCII character set, recovery of the non secret message should be impossible without knowledge of the two bases used in the encoding process. Conversion from/to any other two bases outputs a valid string; It shouldn't be the same one originally encoded unless the two bases match up at the appropriate symbols.

This is relatively "outside the box" thinking: given a graph of numbers (the plaintext), encryption usually will shift the points around on the graph in order to scramble them.

This form of encoding is closer to leaving the points on the graph alone, and instead rearranging the order of the numbers on the sides of the graph. Instead of the x-y axis being labeled 0...255, we choose to keep the order of the numbers of the axis secret.

$\endgroup$
  • $\begingroup$ I don't understand your 2nd paragraph. Could you explain a little bit with a toy example (including e.g. using 16 instead of 256)? $\endgroup$ – Mok-Kong Shen May 31 '16 at 9:12
  • $\begingroup$ @Mok-KongShen I updated the question with an attempt at clarification. Let me know if I need to clarify more. If python makes sense, then code can be found here $\endgroup$ – Ella Rose May 31 '16 at 16:04
  • $\begingroup$ An alphabet of size n maps [0, n-1] to n graphical symbols. It is theoretically unessential how these symbols look like. A substitution scheme is just a specification of a mapping from [0, n-1] to [0, m-1] with n <= m. You could simply do an arbitrary random permutation of [0, m-1] and specify thus a plaintext symbol that has the index i in the plaintext alphabet to correspond to the index j in the ciphertext alphabet (in your own way) thus leading to the ciphertext symbol. If n < m, you could have the benefit of homophones, since one i could correspond to more j's. (Forget the use of bases.) $\endgroup$ – Mok-Kong Shen Jun 1 '16 at 9:37
  • $\begingroup$ @Mok-KongShen Right, the numeric base thing is just one way of looking at it, and is the train of thought that got me started on this idea. What the algorithm actually does is simple, as you note. $\endgroup$ – Ella Rose Jun 1 '16 at 16:27
  • $\begingroup$ What I meant is that the most general case of a substitution is simple and straightforward to specify/implement. Hence IMHO it is not worthwhile to consider for practical purposes special cases that may work as well. $\endgroup$ – Mok-Kong Shen Jun 1 '16 at 18:23
2
$\begingroup$

No, I'm not aware of any cipher that has relied on this. Numeric base conversion is relatively slow. For that performance budget, there are other ways to mix/transform that data that provide greater nonlinearity and diffusion.

$\endgroup$
  • $\begingroup$ And what are these other ways to achieve greater nonlinearity and diffusion more cheaply? $\endgroup$ – maxgalbu Oct 5 '18 at 10:46

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.