StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWill this obfuscation algorithm for a URL shortener work?
text
Body
copied!<p>DISCLAIMER: I am not asking how to make a URL shortener (I have already implemented the "bijective function" answer found <a href="https://stackoverflow.com/questions/742013/how-to-code-a-url-shortener/742047#742047">HERE</a> that uses a base-62 encoded string). Instead, I want to expand this implementation to obfuscate the generated string so that it is both:</p> <p><strong>A) not an easily guessable sequence</strong>, and</p> <p><strong>B) still bijective.</strong></p> <p>You can easily randomize your base-62 character set, but the problem is that it still increments like any other number in any other base. For example, one possible incremental progression might be <code>{aX9fgE, aX9fg3, aX9fgf, aX9fgR, … ,}</code></p> <p>I have come up with an obfuscation technique that I am pleased with in terms of requirement <strong>A)</strong>, but I'm only partially sure that it satisfies <strong>B)</strong>. The idea is this:</p> <p>The only thing that is guaranteed to change in the incremental approach is the "1's place" (I'll use decimal terminology for practicality reasons). In the sample progression I gave earlier, that would be <code>{E, 3, f, R, …}</code>. So if each character in the base-62 set had its own unique offset number (say, its distance from the "zero character"), then you could apply the offset of the "1's place" character to the rest of the string. </p> <p>For instance, let's assume a base-5 set with characters <code>{A, f, 9, p, Z, 3}</code> (in ascending order from 0 to 5). Each one would then have a unique offset of 0 to 5 respectively. Counting would look like <code>{A, f, 9, p, Z, 3, fA, ff, f9, fp, …}</code> and so on. So the algorithm, when given a value of <code>fZ3p</code>, would look at the <code>p</code> and, having an offset of +3, would permute the string into <code>Zf9p</code> (assuming the base-5 set is a circular array). The next incremental number would be <code>fZ3Z</code>, and with <code>Z</code>'s offset being +4, the algorithm returns <code>39pZ</code>. These permutated results would be handed off to the user as his/her "unique URL", who would never see the <em>actual</em> base-62 encoded string.</p> <p>This approach certainly seems reversible; just look at the last character, and perform the same permutation with the negative offset. And I'm thinking that for this reason, it has to still be bijective. But I don't know if this is <em>necessarily</em> true? Are there any edge/corner cases I'm not considering? </p> <p><strong>EDIT :</strong> My intentions are more heavily weighed towards the length of the shortened-URL rather than the security of the pattern. I realize there are plenty of solutions involving cryptographic functions, block ciphers, etc. But I would like to emphasize that I am <em>not</em> asking the best way to achieve <strong>A)</strong>, but rather, "<em>is my offset-approach satisfying <strong>B)</em></strong>".</p> <p>Any holes you can find would be appreciated.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload