Base Encryption: Dynamic algorithms, Keys, and Symbol Set

© 1996-2000

By: Po-Han Lin

Introduction

The following is a description of a new encryption algorithm named Base Encryption. It utilizes the novel concepts of base conversion, symbol remapping, and dynamic algorithms (dynamic operators and dynamic operations). It cannot be cracked by brute forced search, which is the main weakness of many many current encryption systems.

Base Encryption was originally invented on July 10 of 1999. The basic base calculation routines were already in the earlier versions of Virtual Calc since 1996. The current version of Virtual Calc is 2000. Base Encryption utilized many techniques I invented to make it theoretically unbreakable. It is revolutionary in its novel features...

Immune from plain-text-attacks.
Immune from brute-force-attacks.
As secure as OTP
Can utilize throwaway algorithms.
Dynamic Algorithms (operators and operations)
Dynamic Base (symbol set)
Plug-And-Play engine (other cyphers can be augmentated to it)

I am hoping someone uses this information to good use. Virtual Calc 2000 can be used to emulate Base Encryption and can generate simple algorithms for encrypting and decrypting messages.

Base Encryption solves the weakness in todays encryption schemes, namely...

Fixed symbols (base)
Fixed keylengths
Fixed algorithms (fixed number of operations and operators)

All the current modern encryption algorithms utilize fixed symbols for plaintext and cyphertext. What I mean by fixed is that there is a set and limited number of symbols to represent the characters, numbers, and punctuations. In addition, they are usually the same (the plaintext symbols have the same and equivalent counterpart in the cyphertext symbols). Almost all the encryption algorithms rely on a predefined keyspace and length for the encryption/decription keys, and it is usually fixed (number of bits). In addition, the algorithms used by the encryptions are static. There is a predefined number of operatiors, and a predefined order (loops included) of operations. The algorithm stays the same, and the plaintext and cyphertext along with the key are churned through this cypherblock.

The Process

In Base Encryption, 3 main processes needs to be applied to the plaintext and cyphertext in order to convert from one form to another. They are (not necessarily in this order)...

Symbol Remapping
Base Conversion
Core Encryption/Decryption

Each of these processes will be explained as the different pieces of Base Encryption (variable Bases, Dynamic Base Conversion, Dynamic Symbol Remapping, and Dynamic Encryption) are described below...

Variable Bases (Symbol Sets)

The Chinese Newspaper

When people think of Base, they usually think of the base of a number like Hexadecimal, Decimal, Octal, or Binary. It just happens that Hexadecimal is base 16, Decimal is base 10, Octal is base 8, and Binary is base 2. In addition, they each contain that many representable symbols. Hexadecimal happens to use A-F for digits 10-15. Well, if you extend this to high bases, you would need to use more symbols to represent the digits. In this case, you can substitute the whole alphabet, punctuations, and any displayable symbol. I often think of Base as the symbol set of a language. In high enough bases, you can put the entire alphabet in there. Of course, in very high bases you would run out of displayable symbols, and sometimes you need to resort to multibyte character sets like Unicode for displaying them. In the Chinese language (which is like a pictograph language), there are over 50 thousand characters compared to English which is representable in ASCII (less than 256 characters). You can use Chinese Unicode to represent bases in the 50,000 range. Given this information, if you take a Chinese language newspaper and think of it as an encryption algorithm, you would have a hard time decrypting it because there is no direct mapping between chinese characters and the English alphabet unless you get a dictionary and convert on a word by word basis.

Duplicate Symbols

Sometimes, if you do not wish to use Unicode for high bases, you can use duplicate symbols. You can make value 16=F, and 17=F, or maybe 104=F and 222=F, or anything for that matter. For duplicate symbols, the values are important, not the display of the value (the actual symbol you see on the monitor) If an operation were to be applied to it however, then other factors have to be taken into account (see below)

Dynamic Base Conversion

In Base Encryption, the plaintext and cyphertext can be in different bases. Because they are in different bases, a base conversion routine must be used. There are many different types of base conversion routines. One basic one that can be used is numerical base conversion (which is currently supported in Virtual Calc). Numerical base conversion basically converts based on the numerical value of the message. For example, Hexadecimal F can be converted to two Decimal symbols 15. Long messages would be converted like it is one large value in one base. Base conversion involves two things...

Symbol substitution
An algorithm (similar to a few steps in a cypherblock).

Now, it happens that to do numerical base conversion like in Virtual Calc, you need exponent operator, add operator, multipy operator, mod operator, and divide (leaving whole number) operators.

There is a predefined number of steps used to convert a number from base x to base y. (very similar to steps located in a cypherblock). Sometimes the steps involve numbers with infinite digits (6.66666666...). This is especially true when doing numerical base conversion between one base to another that involves a rational number that cannot be divided evenly. So 3.333333333333... may be a number in one base, but after you convert it, it will be totally different (especially using floating point arithmetic). It might go into infinity, it might not (depending on whether it can be representable in a finite number of symbols in the destination base) Note: Virtual Calc 2000 supports configurable precision for floating points calculations of any base you choose.

Be careful to note that there is no direct mapping between one base symbol and another, so you must use a conversion routine. This applies even if the symbols are the same for the first x digits.

Here is an example:

The first base is 10:
The symbols: 0123456789

The second base is 7:
The symbols: 0123456

(Note the first 7 symbols are same)

A symbol like 9 from the first base has no direct mapping to the symbols in the second base. It has to use a base conversion algorithm. In this case numberical base conversion can be used. (Note that you can use any type of base conversion, numerical base conversion is just one of the methods for mapping a value between one base and another). Remember, just one increase in the base (symbol space) will change the answer in the cyphertext.

As for floating point values, sometimes after conversion, you have an infinite number of digits. In the above example, if you enter 2.3 for the second base, and convert it to the first base, you will end up with a number that goes into infinite digits.

Note that for non-numerical base conversion algorithms, you may use duplicate symbols, so the values are important, not the display of the value (the actual symbol you see on the monitor). For duplicate symbols, to take into account the ability to decrypt, the value and representation of the value (symbol) must have a one-to-one correspondence in the cyphertext. If they are not one-to-one, then the conversion routine must take into account symmetric and identity relationships between different values in the plaintext during its conversion process back to the plaintext. Note that this applies the other way around... Having duplicate symbols in cyphertext instead. (These are all good reasearch areas).

Dynamic Symbol Remapping

Before the cyphertext or plaintext is fed into the Dynamic Base Conversion routine, or after it has gone through the Dynamic Base Conversion routine, Base Encryption can apply Symbol Remappings to the input or output. These are basically a rearragement of the symbols in a symbol set (Base). It could be a simple one such as a rotate (shift a position to the left or right), or some wavelet function to have a waveform type of symbol remapping.

Symbol Remapping differs from Base Conversion and Dynamic Encryption (see below) in that for Symbol Remapping, the Symbol Set (Base) has its symbols rearranged in a different order, and the cooresponding symbols in the message are substituted for the correct rearranged symbol. For example, if the Symbol Set for Base 5 is abcde, and the message is "deed", and we remap the Base to aebcd, then the message becomes "cddc". Remember, Dynamic Symbol Remapping means we can remap before it has been base converted, after it has been base converted, or sometime inbetween Dynamic Encryption routines.

Dynamic Encryption Algorithms

Dynamic Encryption involves two dynamic properties...

Dynamic Operators
Dynamic Operations (actual algorithm)

Base Encryption supports Dynamic Operators. An Operator basically takes inputs and performs some operations on it, and produces an output. Messages to be encrypted or decrypted are fed into an operator either in whole or in part based on the Dynamic Encryption Algorithm. Multiple operators can be used one after another and can use shared inputs, or have the input and output piped from one operator to another. An Operator can be generated on the fly as a combination of other operators (operators can be building blocks for more complex operators like components can be building blocks for complex components). Dynamic Operations are basically a combination of Operators being applied to inputs. It can be rule based, or simply sequential: one after another. Examples of Rule based Operations are IF/THEN/ELSE and WHILE/FOR loops. Dynamic Operations are dynamic because the algorithm defined by the operations are not static, and can be changed based on external or internal factors. Internal factors are usually the result of a rule-based operation. External factors may involve existence of certain inputs (external messages).

Simple cases of Dynamic Encryption can be emulated in Virtual Calc 2000 manually. As an example, 1/X*4.3^6 would be taking the inverse of the message (based on its Base value), multiplying it by 4.3, and then taking an exponent of 6 on that value. You can use floating points and any of the standard operators to create new algorithms from scratch. Inverse is a good simple operator to use, as it involves division.

Throw Away Algorithms

Most encryptions these days can utilize throw-away keys. But in Base Encryption, because the algorithms are dynamic, in streaming cyphers or just plain normal encryptions you can change algorithms on the fly based on arbitrary factors. (time, length, etc).

Plug and Play engine

Because the algorithms can be changed on the fly, or created from scratch, you can use adaptive plug-and-play cypher engines with it. Simply plug in twofish, RC6, IDEA, as an augmentative step in the algorithm.

Putting It All Together

So in essence, in order for a message to be encrypted or decrypted in Base Encryption, it would go through the three main processes (not necessarily in any strict order). A simple path might be: a message will be base converted, symbolically remapped, and then dynamically encrypted. As an example, using Virtual Calc 2000, you can manually emulate some parts of Base Encryption to decrypt a message...

Given cyphertext: nphiwva8nas4xf0u8kyuw1etq3hsxb0ks4qbrlr27b6dam8tu4bily.5i

Run Virtual Calc 2000
Click on BASE button.
Enter 36 into Custom Base Box (then press OK).
Enter the above Cyphertext into Expressions Box (you can paste it in).
Follow the message with +33*6/4.5
Press Calculate.
Click on Base Button.
Enter 62 into Custom Base Box (then press OK).

If you followed the steps above correctly, in your Solutions box, you will see the plaintext message I left for you.

Using this same simple example, here are the steps to generate the cyphertext...

Run Virtual Calc 2000
Click on BASE button.
Enter 62 into Custom Base Box (then press OK).
Enter the Plaintext from previous exercise into the Expressions Box (you can paste it in).
Click on Base Button.
Enter 36 into Custom Base Box (then press OK).
Copy the Solution into the Expression Box.
Input *4.5/6-33 after the message in the Expression Box.
Press Calculate.

Note that Symbol Remapping was not demonstrated in this example. You can add it yourself by simply right=clicking on any numeric digit button in Virtual Calc and change the symbol. (You may need to change it to an unused symbol if you wish to swap the value with another symbol/button).

Why Current Encryption Systems Are Insecure

Almost all encryption algorithms these days rely mostly on a subset of ASCII (mostly characters and numbers and some punctuations) to represent the plaintext and the cyphertext. Each unit is usually a byte (a byte can accomodate 256 values, thus the entire alphabet, decimal digits, and punctuations)
There is usually a routine to convert the plaintext into n-bit sized chunks to feed through the cypherblock. This is often done by literally taking the ASCII bytes of the message and combining enough of them to make n-bit chunks. What you get back from the cypherblock is another n-bit chunk that you divide into ASCII bytes (which is the cyphertext). Some algorithms compress the message before breaking it up into n-bit chunks to give it to the cypherblock.

Notice that the base (symbol set) used before the conversion to n-bits and the base (symbol set) of the cypher text are based on the same ASCII representation. There is no symbol remapping done, and there are the same amount of symbols total in the source and destination bases. You simply take the output from the cypherblock and use displayable ASCII values to represent them.

Notice that all encryption algorithms these days also rely on a fixed key length (40bits 56bits 128bits, etc). IDEA, DES, blowfish, RSA, all use a predefined fixed keylength. The symbol set (Base) of the cyphertext and plaintext also contain one-to-one relationship between symbols. A-Z and A-Z, and there are the same number of symbols in both.

Brute Force Search

Fixed keylength cyphers and fixed symbols cyphers can be cracked by brute force search on the key and algorithm. For example, a plaintext message like...

"How are you doing?"

and an encryption key is is sent through a cypherblock and produces a message

"8j2d$9898#8oismkoiiog298jsdnfoig[eiuwe"

as output. In order to get the original message from the cyphertext, you would use a descryption key and pipe the cyphertext and decryption key through the cypherblock. Without going into details, there are some variations on the keys (like public keys, and symmetric keys), but essentially you can permutate through the values of the decryption key to get the original plaintext. Lets say given a 56bit key, to brute force search the keyspace, you would start with...

0000000000 0000000000 0000000000 0000000000 0000000000 000000

and end at

1111111111 1111111111 1111111111 1111111111 1111111111 111111

You pipe each of these key values through the fixed keylength cypherblock, and eventually you will get your original plaintext message.

In a fixed keyspace you can permutate through the values because there is a linear relationship between one value and the next, and there is a beginning and ending value for you to permutate through. For most encryption keys, the beginning and ending keylength is fixed (56bits, 128bits, etc). In addition, there is a linear relationship between one value of a key to the next (essentially x+1).

Uniqueness of Base Encryption

Differences With Other Encryption Systems

As outlined previously, Base Encryption supports the following unique properties...

It supports various bases (symbol sets).
It utilizes symbol substitution for remapping (a basic form of encryption, dating back to Caesar, and the Roman empire)
It uses base conversion (numerical, or any algorithm you can think of) for basic base conversion (this can be exclusive of the symbol remapping).
It uses any combination of operatiors as the actual heavy duty encryption. (you can use rotation, shift, add, subtract, invert, a compression algorithm, another cypher, ANYTHING).

One main feature that pops up again and again is the dynamic nature of all the properties that it supports.

The Base Encryption algorithm used is dynamic, it can be changed on the fly. Whereas all the other cypherblock encryptions use standard routines (rotate, xor, etc) in a fixed sequence. Remember, dynamic algorithm is more secure than static algorithms.
Almost all the encryption algorithms these days requires the message to be broken up as mentioned before, but note that in Base Encryption, you need not break the message up into n-bit sized chuncks. You can feed the whole message into Base Encryption at once. It basically supports dynamic bits, which is a unique property good for streaming cyphers. The bit size is variable, and can be affected by base (symbol set), algorithm used before and after base conversion, as well as how the message was broken up.

Streaming Cyphers

Base encryption can be utilized as an unbreakable streaming cypher. Because you can change the algorithm on the fly, you can have the first segment use algorithm 1, base x, second segment use algorithm 2, base y, etc.

Why Base Encryption Is Secure

Garage Door Analogy

Automatic garage door openers relies on a remote control sending it an infrared signal of a fixed sequence of bits (around 8 usually). That 8 bits is the key to opening the garage door. It also depends on a fixed length of the received bits. Sending it the wrong number of bits will not open it. For example...

If the combination is
00001101
And you send
000001101
or you send
1101
it will not open it.

Note in the example above, they are essentially the same value, but the lengths are different. There is a fixed length that the garage door opener expects. So you have to send it exactly that many amount of bits, or it is not going to open.

In this analogy, knowing the length of bits (8) allows you to easily permuate through the keyspace beginning at 00000000 and ending at 11111111. What if you did not know the length of the bits? In this case s/he has to permutate starting at 1 bit, then work to 2 bits, then work to 3 bits, then work to 4 bits, etc. This is exponentially expensive (more so than simply permutating through a known keylength).

As a max 256 bit example, permutating through the values of the keys requires starting with 1 bit, and continuing to to 256 bits. You must go through the values for EACH bit increase (rather than the today's weak cyphers starting point at 256 bits (value 0) and end at 256 bits (value 256). This is one layer in the security against brute-force-attacks.

Note in this example it involves just one unknown value that can go into infinity. In this specific garage door example, you can associate finding the combination as ONE layer of protection in Base Encryption: namely the Base. You must know the correct base to convert to before you can begin the Dynamic Encryption, Base Conversion, and other stuff.

Base Encryption has many of these layers, thus it is secure from brute force attacks (more on this later).

NP

In math there are problem domains called NP (Non-Polynomial). There are also the concepts of tractable and intractable problem domains.
Tractable problems are problems you can solve using brute force, which is essentially permutating through all the values of a problem until a solution is found. (This is very similar to permutating through the values of an encryption key until you get the right one).
Intractable problems are problems that cannot be solved using brute force techniques (i.e. you are not able to permutate through the values because of certain infinite properties associated with the values). It does not matter how fast or how many computers you use, it is not solvable using brute force attacks (in essence, an NP problem).

In intractable NP problems, it is not possible to permutate through the values because going from one value to the next may be a step requiring an exponential or infinite mini-steps. In addition, sometimes you do not know the keyspace you are traversing, thus you must begin at ground zero.

In Base Encryption (with its use of dynamic operators, dynamic operations, and dynamic bases, it is not possible to permutate through the values. There are an infinite combinations of operators (its dynamic, and there is not fixed number of them, and there is no fixed maximum number of operations you can use) which can be used for the algorithm. This is in addition to symbol remapping and base conversion algorithms.

You can use billions and billions of computers, and it is still not tractable.
To illustrate how NP intractable problems look like, I will give some examples...

How many games are out there? Infinite (more are being created every day).
What order can you play two games? Infinite (because you can replay one game, then go to game two, and come back to game one, and keep playing until next year, or maybe after ten years)
What order can you play all the games? NP (you are combining the two problems with infinite domains. Going from one game to the next is dependent on an infinite value that you cannot permutate through.

When you have infinite with infinite (like the example above), no number of computers in the world short of infinite can solve it (and even then you have no guarantee of reaching an answer).

In the example above if you fix the number of games in existence (lets say two), you still have an infinite number of orders of playing them. If you fix the order of playing the games (lets say only sequentially from game one to game two), it is also infinite because there is no finite number of games.
When you put them together, it becomes simply intractable.

Now map this analogy with the order of operators, number of operators, the base (to infinity), the conversion algorithm used between base, the symbol set of the original base to the destination base, the symbol remapping strategies, you have an intractable problem. It is NP, and no amount of computers in the world could break it. Even the one-time pad relied on just one symbol space!

This is very similar to the Heisenberg uncertainty principle and the quantum mechanic duality problem. The more you know one value, the less you know the other. The more you can pinpoint the location, the less you know about the speed. And vice versa.

See: Heisenberg, W.
"The Perceptible content of the Quantum Theoretical Kinematics and Mechanics"
"Uber den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik"
Zeitschrift fur Physik 43, 172-198 1927.
(Heisenberg was somewhat disturbed by his discovery that simultaneous observations of complementary quantities cannot be both infinitely accurate, and went to Copenhagen to discuss this with Niels Bohr, who argued Heisenberg to publish.)

See: Heisenberg, W.
"Die Rolle der Unbestimmtheitsrelationen in der mordernen Physik"
Monatshefte fur Mathematik und Physik 38, 365-372, 1931.

Cracking Base Encryption: Fruitless Effort

To crack Base Encryption, you need to guess...

The Base of the cyphertext (now did he use base 26? or standard ASCII, or some large base with duplicates? Or a small English subset of Chinese Unicode?)
The Base of the plaintext (now did he use base 26? or standard ASCII, or some large base with duplicates? Or a small English subset of Chinese Unicode?)
The conversion algorithm used to convert between the above two bases. (numerical base conversion like Virtual Calc 2000? Or another type of conversion?)
The Symbol Remapping. Any substitutions used?
The actual algorithm used. (shift, rotate, add, 1/x, a dynamically generated one?)
The order. Was the Symbol Remapping done before or after Base Conversion?

Immune from brute-force-attacks

In addition to the exponential permutation time of dynamic key lengths, another property of Base Encryption that thwarts Brute-Force attacks is the inability to test against the engine to see if you have the right key. < Because the algorithms can be dynamic, and multiple algorithms can derive the same You don't know when you have found the answer. It is immune from brute-force-attacks on the basis the INABILITY for you test against the engine and know when you have the right key.

Immune from plain-text attacks

Because the algorithms can be dynamic, and multiple algorithms can derive the same cypherkey or plaintext, chosen plain text attacks cannot test against the engine for patterns and weaknesses. As an example, there are an infinite ways to generate 12345. (12344+1, 12343+1+1, 12345+5-5, 100*100+2345, etc). Dynamic properties twart attacks like these.

In essence, Base Encryption is secure. Base Encryption utilizes advanced dynamic properties and is within an NP intractable problem.

Conclusion

So in essence cracking Base Encryption is not possbile because...

Base Encryption is within an intractable NP domain.
It is not possible to permutate through a keyspace like an 8bit garage door opener. In Base Encryption, if you have one value correct, it is still not going to crack it because other dependent values are not known and have an infinite number of values.
Hardware stuff like the EFF Deep Cracker cannot be built that can take advantage of brute force searching techniques to break Base Encryption. Even having millions of computers throughout the internet will have no affect on cracking Base Encryption (like the one at distributed.net)
Base Encryption algorithms are dynamic. You can change algorithms on the fly. Most standard cracking algorithms rely on a fixed algorithm (DES, RSA, IDEA, etc all have fixed algorithms). Changing the algorithm in Base encryption is as simple as changing the operators. (and you can create any, like 4*pi*x, 1/x, or use any lossless compression algorithm for the daring). Good ones to use are floating points (Virtual Calc does floating point calculations in any base) because they can go into infinite digits You can even integrate an existing modern encryption algorithm as an operator.
Because the potential cracker does not know the base and the algorithms involved (let alone the beginning and end segments), he can't brute force search through it, and even lets say he/she permutates through base 500 starting from base 2, s/he still would not be able to know if the message is true unless each is examined one by one and manually pick out to be ones that looks like it has meaning.

In conlusion, Base Encryption with its use of variable bases, dynamic base conversion routines, symbol remapping, and dynamic algorithms is the only encryption algorithm that is as secure as one-time pad (may be even more so, because even in one-time pad you know the symbol space). All the encryption algorithms these days are fixed in one way or another, and whenever you have anything that is fixed, it can be cracked using brute force techniques in a given time period.