Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Japh algebra, GF(128) edition

by ambrus (Abbot)
on Oct 02, 2010 at 21:13 UTC ( #863110=obfuscated: print w/replies, xml ) Need Help??

Did you know you could evaluate a polynomial over GF(128) in perl with pack and unpack and tr? Here's how.

sub h { $_ = $_[0] = pack b208, 0 . unpack b362, $_[0]; tr/\0-\c?/\0/; tr/\0/\377/c; $_ } for (split //, "k6sNP2B}({ambrusLB%Ox)Z]n0*zf\0I3") { $y = $r; $v = join $r = '', a .. z; $r ^= h($r) & "\217" x 26 ^ h($v) & $y for 0 .. 6; $r ^= $_ x 26; } print $r;

This code is based on the same idea as Dollar Plus, but written in a different style, so some of the credit goes to martin.

Update: if you prefer one of these unreadable blocks of code, you can of course write this that way too (Update: reformatted blob from four lines to three.)

sub h($){($_=$_[0]=pack b208,0 .unpack b362,$_[0])=~tr/\0-\c?/\0/;tr /\0/\377/c;$_}do{$y=$r;$v=join$r='',a..z;$r^=h$r&"\217"x26^h$v&$y for 0..6;$r^=$_ x26}for"k6sNP2B}({ambrusLB%Ox)Z]n0*zf\0I3"=~/./g;print$r

Update: removed lots of spaces from end of lines of formatted code.

Replies are listed 'Best First'.
Re: Japh algebra, GF(128) edition
by BrowserUk (Pope) on Oct 02, 2010 at 21:46 UTC

    Could you explain, (or point to an explanation of), (preferably in layman's terms), the annotation "GF(128)"?

    I tried a search, but the term matches too many things to know where to start.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Let's start from a bit farther. This series of obfus works by storing a polynomial and evaluating it at different places to get the message.

      For example, suppose you wanted to print the message 3, 8, 0. You could then create the polynomial f(x) = 3 + 11.5*x - 6.5*x**2, for which f(0), f(1), f(2) gives the values you want, and write code like this to evaluate that polynomial.

      for $x (0 .. 2) { $y = 0; $y = $_ + $x * $y for qw"6.5 -11.5 3"; say $ +y; }

      Now the problem with this method is numeric precision: if you wanted to do the same thing if you want to get 26 values (the character codes of a 26 character long message), you either couldn't do it with floating point at all, or you'd have to give the coefficients to lots of decimal digits of precision.

      There's however an easy solution, which is to compute the polynomial modulo a convenient prime, namely 127. This is what Japh algebra, Japh algebra revisited, and ASCII arithmetic does (read the first one, for that has almost no obfuscation layer apart from this). We call this computing over the finite field of size 127, that is, over GF(127). (The name GF stands for Galois field originally.)

      Now, computing over a prime field like GF(127) is easy because you just add or multiply two elements by adding or multiplying them as integers and then taking the result modulo 127. The obfu is thus as simple as

      for $x (0 .. 25) { $y = 0; ($y = $_ + $x * $y) % 127 for @coeffs; say +$y; }

      Now, if a field is not a prime field, such as GF(128), then it's not so simple to do the computation, though it's also not too complicated as the brevity of the obfus show in hindsight. That's why I wondered what such an obfu would look like before martin wrote one, and before I dreamt this one.

      As for why I asked for GF(128) instead of some other field, the reason is brevity. To make the code simple enough, the field should be large enough that each element could encode a character of the output, but small enough that each element in the coefficient vector can be stored as a single character in the obfu. (There could be a challenge here though, seeing whether it's possible to do calculations over GF(125) or similar in just a few lines, or using two characters per field element for a larger field.)

      Update: hide all behind spoiler tags.

        (The name GF stands for Galois field originally.)

        Ah right! Those special French tobacco farms :)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: obfuscated [id://863110]
Approved by planetscape
Front-paged by planetscape
and a log crumbles through the grate...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2017-04-28 06:01 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (519 votes). Check out past polls.