john-users - one decimal digit adder using rules (2+3 -> 5)

Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140420150839.GA19097@openwall.com>
Date: Sun, 20 Apr 2014 19:08:40 +0400
From: Aleksey Cherepanov <aleksey.4erepanov@...il.com>
To: john-users@...ts.openwall.com
Subject: one decimal digit adder using rules (2+3 -> 5)

I made an adder using rules. It works for 2 numbers of 1 decimal digit
each. I'll describe two approaches.

1) Make a lot of rules like "if digit1 is ... and digit2 is ... then ...".

To express statement like "if condition then action1 else action2" one
could use two rules:
reject if not condition, action1
reject if condition, action2

So I made 100 rules like the following:
/+ {\[} M \[ /2 X010 \] /3 Az"5" \[

/+ {\[}  # drop +, so 2+3 -> 23
M \[     # remember digits and drop the first
/2       # reject input where the second digit is not equal to 2
X010 \]  # put the first digit back and drop the second
/3       # reject input where the first digit is not equal to 3
Az"5" \[ # put result into the word and drop second digit

So 2, 3 and 5 should be varied.

Here is a one-liner to do the job:
perl -e 'for $i (0 .. 9) { for $j (0 .. 9) { $c = $i + $j; print qq#/+ {\\[} M \\[ /$i X010 \\] /$j Az"$c" \\[\n# }}'

This variant handles carry.

2) Somehow transform digits to join them without rejects. We could use
dummy values to avoid rejects but still have branching when we use
search.

I'll subtract 1 from the first digit and add 1 to the second digit
many times. Loops could be expressed being just unrolled: I search for
9, replace it with 8 and add 1 to the second digit, then I search for
8, replace it with 7 and add 1 to the second digit, and so on. Dummy
values could be used to make variable amount of effective iterations:
I add "9a", so some first iterations work on the dummy part. I encode
the second digit so it is messed with the first digit in case of
"233f".

Iterations /3 ... and /2 ... could look like:
2t3i
2t2o
1y2o

The rule:
/+ {\[} M s0w s1e s2r s3t s4y s5u s6i s7o s8p s9\[ \[ X010 Az"9a" va01 /9 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /8 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /7 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /6 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /5 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /4 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /3 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /2 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc /1 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc sw0 se1 sr2 st3 sy4 su5 si6 so7 sp8 s\[9 \[ \]\]

/+ {\[} # drop +, so 2+3 -> 23

# Then we replace the second digit like "12...9" -> "we...[" to
# protect it from search for digits.
M s0w s1e s2r s3t s4y s5u s6i s7o s8p s9\[ \[ X010

Az"9a" # Add dummy, so search 9 does not fail anyway
va01   # Store -1 to make p+1 later

# The main block:
/9 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc
...
/1 vbp0 vcba R M L Dc Xc1c L M R Xb1b Dc

# In detail (the tail is described later):
/9            # Search for digit, it may be actual digit or dummy
vbp0 vcba     # Store position and position+1
R M L Dc Xc1c # Shift right (by keyboard) the second digit: d++
L M R Xb1b Dc # Shift left (by keyboard) the first digit: d--

# The tail:
sw0 se1 sr2 st3 sy4 su5 si6 so7 sp8 s\[9 # Reverse protective encoding
\[ \]\] # Cut the first digit and dummy out
# The end

Commands to try:
echo 2+3 | ./JohnTheRipper/run/john -ru=my -pipe -stdout
for i in $(seq 0 9); do for j in $(seq 0 9); do printf "$i + $j = "; echo "$i+$j" | ./JohnTheRipper/run/john -ru=my -pipe -stdout 2>/dev/null; done; done

When results if higher than 9 we get ]. No carry in this implementation.

It would be easier to put values directly but only the first digit
could be transformed that way.

It does not look like rules have good primitives to make efficient
adder. Though one could try to use cases as bits (TN toggles bit at
position N). It should be interesting to try. Also one should be able
to use M and variables to implement a stack: push: store length, add
memorized value to the current one, remember, remove added value.

Problems I had:
- I was really confused about XNMI rules, somehow I thought M is the
second position but X000 did not work and my rules worked very
strange. But M is the length. Maybe doc/RULES could tell about it
earlier near "substring NM".
- Shifts are limited, so L does not shift 'a' and R does not shift
'\'. So my temporary shifts broke values with wrong encoding. That's
why I use wer... and not asd...
- Shifts could not be applied to a single position so I had to use
construction like: shift M shift_back Dp Xp1p.

Thanks!

-- 
Regards,
Aleksey Cherepanov
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.