Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to visually encrypt (make the information uninterpretable by a non-prepared human) a natural number (known to be below some x) representing it as a much bigger, seemingly (for an unprepared observer) random (so just a+x doesn't work) natural number and then decrypt it back.


a = the source value
0 < a < x
b = the encrypted value
x < b < y
y = 2147483647

UPDATE: @chris-taylor has answered the question, but more answers are still welcome. For example (my dilettantish expectations on fancy math suggest it can be possible and easy for math geeks) it would be cool to have a simple formula (without a huge key mapping) to solve the task beating the law of b2(a2) being always greater or always smaller than b1(a1) when a1 < a2. But this is not necessary, I am just curious.

share|improve this question
    
You need to read about steganography. Optimally, there would be a key needed to even be able to show that there is a message (i.e. smaller number) hidden. –  Paŭlo Ebermann Oct 16 '11 at 23:38
add comment

1 Answer

up vote 2 down vote accepted

It depends on how 'random' you want it to appear. You could use a combination of multiplication and linear shift:

$$b = ha + k$$

and then the decrypting is easy:

$$a = (b - k) / h$$

For this to satisfy your condition that $b<y$ you need to choose $h$ and $k$ such that $hx+k<y$, which gives you quite a bit of freedom.


Or you could use multiplication modulo $y$, such as

$$b = ma \mod y$$

To decrypt you multiply by any inverse of $m$, i.e. any number for which $nm=1$ $(\textrm{mod } y)$, to get

$$a = nb = nma = a \mod y$$

However, this method doesn't guarantee that $b>a$ (although if $x$ is sufficiently small then 'most of the time' you will have $b>a$).


Since you are coming at this from a programming point of view, perhaps the best method is to store two maps (or dicts, depending on your language) encrypt and decrypt such that the result of encrypt.get(a) is greater than x and the expression decrypt.get(encrypt.get(a)) == a is true for all a. Then your encryption can be as random-looking as it is possible to be.

This does depend somewhat on the size of x. A map with a million keys is small fry, but a map with a billion keys is starting to take up decent amounts of space.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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