Encryption algorithm clarification

Question

I am trying to create and encryptor and parser for my personal project.
Suppose I encrypt latin alphabet as follows:

a = a;
b = ab;
c = aab;
....
z = a...ab

In this case the string "aaab" can be decrypted in multiple ways:
ac, aab

But if I encrypt the alhabet as follows:

a = a;
b = ab;
c = abb;
....
z = a...bb

In this case any string can be decrypted in one and only unique way.

Is there an algorithm or theorem that describes this behavior? Will this be a correct encryption or for a very long strings I can somehow gain ambiguity.

You're referring to properties of classical ciphers more than modern encryption. Your question is more on topic on the cryptography site. Modern encryption is way past constructs like that. — Luke Joshua Park
– Luke Joshua Park, Commented Jun 20, 2018 at 10:23
"Will this be a correct encryption": besides the fact that it is unacceptably non-compact, this "encryption" is cracked in a second. — user1196549
– user1196549, Commented Jun 20, 2018 at 10:31

yeputons · Accepted Answer · 2018-06-20 10:38:47Z

2

You're looking for uniquely decodable codes.

One example of uniquely decodable codes are prefix-free codes. Meaning, there are no two characters A and B such that encode(A) is a prefix of encode(B). That is relatively easy to check.

If your code is prefix-free, it can be easily decoded: you just take the only prefix of the encoded string which corresponds to some character. Say, Huffman code is a popular example of prefix-free code used for compression.

The converse is not true, though, as your second code is not prefix-free, but is still uniquely decodable. There are some algorithms to check whether code is uniquely decodable (e.g. in this presentation), but I'm not aware of any beautiful reformulation. One requirement for the code to be uniquely decodable is Kraft–McMillan inequalily, but it can hold for non-uniquely decodable codes as well (e.g. your first code).

answered Jun 20, 2018 at 10:38

yeputons

9,3081 gold badge37 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Eduard Rostomyan Over a year ago

but here, a is a prefix for ab, ab is a prefix for abb. ist it?

yeputons Over a year ago

@EduardRostomyan that's right: a, ab, abb, ... code is not prefix-free, but it's still uniquely decodable.

Eduard Rostomyan Over a year ago

so if i change a = a to a = b in first example, it will be prefix free and uniquely construable?

Collectives™ on Stack Overflow

Encryption algorithm clarification

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related