## Elsie Four

### March 27, 2018

My solution doesn’t work; it encrypts properly, according to the example in Kaminsky’s appendix, but doesn’t decrypt, and I don’t know why. Here is my code, which ignores the header, just as Kaminsky does:

; elsie four (define (drop n xs) (let loop ((n n) (xs xs)) (if (or (zero? n) (null? xs)) xs (loop (- n 1) (cdr xs))))) (define (make-matrix rows columns . value) (do ((m (make-vector rows)) (i 0 (+ i 1))) ((= i rows) m) (if (null? value) (vector-set! m i (make-vector columns)) (vector-set! m i (make-vector columns (car value)))))) (define (matrix-ref m i j) (vector-ref (vector-ref m i) j)) (define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x)) (define (string->ints str) (define (c->i c) (cond ((char=? c #\#) 0) ((char=? c #\_) 1) ((char<=? #\2 c #\9) (- (char->integer c) (char->integer #\0))) ((char<=? #\a c #\z) (- (char->integer c) (char->integer #\a) -10)) ((char<=? #\A c #\Z) (- (char->integer c) (char->integer #\A) -10)) (else (error 'string->ints "unrecognized character")))) (map c->i (string->list str))) (define (ints->string ints) (define (i->c i) (cond ((or (< i 0) (< 35 i)) (error 'ints->string "unrecognized character")) ((= i 0) #\#) ((= i 1) #\_) ((< i 10) (integer->char (+ (char->integer #\0) i))) (else (integer->char (+ (char->integer #\A) i -10))))) (list->string (map i->c ints))) (define (initialize-state key) (let ((xs (string->ints key)) (state (make-matrix 6 6))) (do ((k 0 (+ k 1)) (xs xs (cdr xs))) ((null? xs) state) (matrix-set! state (quotient k 6) (modulo k 6) (car xs))))) (define (find s x) (let loop ((k 0)) (let ((r (quotient k 6)) (c (modulo k 6))) (if (= (matrix-ref s r c) x) (values r c) (loop (+ k 1)))))) (define (advance-state state i j r c x y ct) (let ((t (matrix-ref state r 5))) (matrix-set! state r 5 (matrix-ref state r 4)) (matrix-set! state r 4 (matrix-ref state r 3)) (matrix-set! state r 3 (matrix-ref state r 2)) (matrix-set! state r 2 (matrix-ref state r 1)) (matrix-set! state r 1 (matrix-ref state r 0)) (matrix-set! state r 0 t)) (set! c (modulo (+ c 1) 6)) (when (= x r) (set! y (modulo (+ y 1) 6))) (when (= i r) (set! j (modulo (+ j 1) 6))) (let ((t (matrix-ref state 5 y))) (matrix-set! state 5 y (matrix-ref state 4 y)) (matrix-set! state 4 y (matrix-ref state 3 y)) (matrix-set! state 3 y (matrix-ref state 2 y)) (matrix-set! state 2 y (matrix-ref state 1 y)) (matrix-set! state 1 y (matrix-ref state 0 y)) (matrix-set! state 0 y t)) (set! x (modulo (+ x 1) 6)) (when (= c y) (set! r (modulo (+ r 1) 6))) (when (= j y) (set! i (modulo (+ i 1) 6))) (set! i (modulo (+ i (quotient ct 6)) 6)) (set! j (modulo (+ j (modulo ct 6)) 6)) (values state i j r c x y)) (define (encrypt key nonce plaintext signature) (let ((state (initialize-state key)) (i 0) (j 0)) (let loop ((ps (string->ints (string-append nonce plaintext signature))) (state state) (i i) (j j) (cs (list))) (if (null? ps) (string-upcase (string-append nonce (ints->string (drop (string-length nonce) (reverse cs))))) (call-with-values (lambda () (find state (car ps))) (lambda (r c) (let* ((x (modulo (+ r (quotient (matrix-ref state i j) 6)) 6)) (y (modulo (+ c (modulo (matrix-ref state i j) 6)) 6)) (ct (matrix-ref state x y))) (call-with-values (lambda () (advance-state state i j r c x y ct)) (lambda (state i j r c x y) (loop (cdr ps) state i j (cons ct cs))))))))))) (define (decrypt key nonce ciphertext) (let ((state (initialize-state key)) (i 0) (j 0)) ; encrypt nonce (to set initial state for decryption) (let loop ((ps (string->ints nonce)) (state state) (i i) (j j)) (when (pair? ps) (call-with-values (lambda () (find state (car ps))) (lambda (r c) (let* ((x (modulo (+ r (quotient (matrix-ref state i j) 6)) 6)) (y (modulo (+ c (modulo (matrix-ref state i j) 6)) 6)) (ct (matrix-ref state x y))) (call-with-values (lambda () (advance-state state i j r c x y ct)) (lambda (state i j r c x y) (loop (cdr ps) state i j)))))))) ; decrypt message text and signature (let loop ((cs (string->ints ciphertext)) (state state) (i i) (j j) (ps (list))) (if (null? cs) (string-upcase (ints->string (reverse ps))) (call-with-values (lambda () (find state (car cs))) (lambda (x y) (let* ((r (modulo (- x (quotient (matrix-ref state i j) 6)) 6)) (c (modulo (- y (modulo (matrix-ref state i j) 6)) 6)) (pt (matrix-ref state r c))) (call-with-values (lambda () (advance-state state i j r c x y (car cs))) (lambda (state i j r c x y) (loop (cdr cs) state i j (cons pt ps))))))))))) (define key "XV7YDQ#OPAJ_39RZUT8B45WCSGEHMIKNF26L") (define nonce "SOLWBF") (define plaintext "IM_ABOUT_TO_PUT_THE_HAMMER_DOWN") (define signature "#RUBBERDUCK") > (encrypt key nonce plaintext signature) "SOLWBFI2ZQPILR2YQGPTLTRZX2_9FZLMBO3Y8_9PYSSX8NF2" > (decrypt key "SOLWBF" "I2ZQPILR2YQGPTLTRZX2_9FZLMBO3Y8_9PYSSX8NF2") "ZCIO5NFFSK8GHJ4LR3F8QNNVSK88VJH3JIEKIUQ8_6"

I’ve checked the decryption code several times, carefully, and don’t see a problem. I know that `encrypt`

and `advance-state`

work properly, and `advance-state`

is the same for both encryption and decryption, so the problem is in the `decrypt`

function, but I don’t see the problem. I’ll keep working on it; maybe one of you will spot the problem first. You can run the code at https://ideone.com/DEfZJ8.

By the way, I can never make these “hand-operable” ciphers work by hand. I don’t know if I lack concentration, or get too easily distracted, but my attempts to use manual ciphers always fail. For Elsie Four, I tried to encrypt the sample message three times, and my best result was to get the first fourteen characters right (and six of those were the nonce).

Here is a rather messy and verbose, but working, implementation in

standard Scheme. It tries to generalize to table-sizes other than

6×6, but I haven’t tested that part yet.

Here is a Forth implementation suitable for Gforth 0.7.3:

\ Elsie-Four (LC4), Copyright 2018 etb, License: GPLv3+

CREATE K 36 ALLOT \ Key buffer

CREATE S 36 ALLOT \ State buffer

CREATE M 0 , \ Marker

->INT ( c -- n)

DUP [CHAR] # = IF DROP 0 ELSE

DUP [CHAR] _ = IF DROP 1 ELSE

DUP [CHAR] 2 >= OVER [CHAR] 9 <= AND IF [ CHAR 2 2 - ]L - ELSE

DUP [CHAR] a >= OVER [CHAR] z <= AND IF [ CHAR a 10 - ]L - ELSE

DUP [CHAR] A >= OVER [CHAR] Z <= AND IF [ CHAR A 10 - ]L - ELSE

." Warning: mapping '" EMIT ." ' to '_'" CR 1

THEN THEN THEN THEN THEN ;

->CHAR ( n -- c) >R

S" #_23456789abcdefghijklmnopqrstuvwxyz" R@ <

IF [CHAR] * ELSE R@ + C@ THEN R> DROP ;

CREATE BUF 256 ALLOT CREATE B BUF ,

B0 BUF B ! ; : .B BUF B @ BUF - TYPE ;

B, B @ C! [ 1 CHARS ]L B +! ;

CREATE A 0 ,

C@A+ ( -- c) A @ C@ 1 CHARS A +! ;

A-C! ( c --) A @ 1 CHARS - TUCK C! A ! ;

RIGHT-ROTATE ( row --) 6 * S + A !

C@A+ C@A+ C@A+ C@A+ C@A+ C@A+ >R

A-C! A-C! A-C! A-C! A-C! R> A-C! ;

C@A6+ ( -- c) A @ C@ 6 CHARS A +! ;

A6-C! ( c --) A @ 6 CHARS - TUCK C! A ! ;

DOWN-ROTATE ( col --) S + A !

C@A6+ C@A6+ C@A6+ C@A6+ C@A6+ C@A6+ >R

A6-C! A6-C! A6-C! A6-C! A6-C! R> A6-C! ;

S[] ( n -- c) S + C@ ;

SFIND ( c -- n) >R

0 BEGIN DUP S[] R@ <> WHILE CHAR+ REPEAT R> DROP ;

+S ( n n' -- n'') \ Add indices within the state matrix

6 /MOD ROT 6 /MOD ROT

+ 6 MOD 6 * >R + 6 MOD R> + ;

-S ( n n' -- n'') \ Subtract indices within the state matrix

6 /MOD ROT 6 /MOD ROT

- 6 MOD 6 * >R SWAP - 6 MOD R> + ;

\ Rather than maintain row and column indices for various markers,

\ just keep track of the character, and search, via SFIND, for the

\ index in S when needed.

UPDATE ( C P --)

SFIND 6 / RIGHT-ROTATE \ rotate row of P

DUP SFIND 6 MOD DOWN-ROTATE \ rotate column of C

M @ SFIND +S S[] M ! ; \ adjust marker

CIPHER ( c --) ->INT

DUP SFIND M @ ( P P' M)

+S ( P C') S[] TUCK ( C P C)

->CHAR B, UPDATE ;

PLAIN ( c --) ->INT

DUP SFIND M @ ( C C' M)

-S ( C P') S[] DUP ( C P P)

->CHAR B, UPDATE ;

(ENCRYPT) ( c-addr u) BOUNDS ?DO I C@ CIPHER LOOP ;

(DECRYPT) ( c-addr u) BOUNDS ?DO I C@ PLAIN LOOP ;

RESET K S 36 CMOVE 0 S[] M ! ; \ Reset the state matrix and marker

ENCRYPT ( nonce u1 header u2 plaintext u3 sig u4)

RESET

2>R 2>R 2SWAP \ save plaintext/sig for later, setup nonce

(ENCRYPT) B0 \ encrypt the nonce and ignore

(ENCRYPT) B0 \ encrypt header, if any, and ignore

2R> 2R> 2SWAP \ restore sig/plaintext

(ENCRYPT) \ encrypt the plaintext

(ENCRYPT) \ append the encrypted sig

CR ." Ciphertext: " .B CR ;

DECRYPT ( nonce u1 header u2 ciphertext u3)

RESET

2SWAP 2ROT \ save ciphertext for later, setup nonce

(ENCRYPT) B0 \ encrypt the nonce and ignore

(ENCRYPT) B0 \ encrypt header, if any, and ignore

(DECRYPT) \ decrypt the ciphertext

CR ." Plaintext: " .B CR ;

S. S A ! 6 0 DO 6 0 DO C@A+ ->CHAR EMIT LOOP SPACE LOOP ;

M. SPACE M @ SFIND 6 /MOD . SPACE . SPACE ;

TRACE ( c-addr u) CR RESET

." State" 38 SPACES ." i j pt ct" CR

S. M. CR BOUNDS ?DO

I C@ CIPHER

S. M. I C@ EMIT 2 SPACES B @ 1 CHARS - C@ EMIT CR

LOOP ;

\ Convenience syntax

SEND

BL PARSE \ nonce

BL PARSE \ header

BL PARSE \ plaintext

BL PARSE \ sig

ENCRYPT ;

RECEIVE

BL PARSE \ nonce

BL PARSE \ header

BL PARSE \ ciphertext

DECRYPT ;

`PRIV-KEY ( " ccc" --)`

BL WORD COUNT

36 <> IF DROP ." ERROR: Key must have length 36" CR QUIT THEN

A ! 36 0 DO C@A+ ->INT K I + C! LOOP ; IMMEDIATE

An example of use:

$ gforth elsie-four.fth

PRIV-KEY XV7YDQ#OPAJ_39RZUT8B45WCSGEHMIKNF26L

s" solwbf" s" " s" im_about_to_put_the_hammer_down" s" #rubberduck" ENCRYPT

Ciphertext: i2zqpilr2yqgptltrzx2_9fzlmbo3y8_9pyssx8nf2

ok

s" solwbf" s" " s" i2zqpilr2yqgptltrzx2_9fzlmbo3y8_9pyssx8nf2" DECRYPT

Plaintext: im_about_to_put_the_hammer_down#rubberduck

ok

SEND nonce header this_is_an_amazing_message

#theartist#theartistCiphertext: wn9pfizu9c3cjc8ul3bkwazx#xhcm8ubj_2p8d

ok

RECEIVE nonce header wn9pfizu9c3cjc8ul3bkwazx#xhcm8ubj_2p8d

Plaintext: this_is_an_amazing_message

ok

And of course the formatting comes out less than desirable. So here’s the same code in a git repo: https://notabug.org/bavier/elsie-four/src/master/elsie-four.fth

At https://github.com/exaexa/ls47 you can find according Python 3 code (LS47.py) with many command line options.

They allow to switch between LC4 and its enhancement LS47, and to use different paddings.

Here’s a solution in Python using NumPy.

The program omits unused calculations from the paper’s right-rotation and down-rotation subroutines.

Output: