Skip to content

Instantly share code, notes, and snippets.

@shirok
Created July 15, 2012 04:57
Show Gist options
  • Save shirok/3115076 to your computer and use it in GitHub Desktop.
Save shirok/3115076 to your computer and use it in GitHub Desktop.
;;
;; Implementation of John Nash's enciphering-deciphering machine described in
;; http://www.nsa.gov/public_info/_files/nash_letters/nash_letters1.pdf
;;
(use gauche.sequence)
(use gauche.generator)
(use srfi-43)
;; The 'key' of this machine is a configuration of Permuter-Reverser (P/R)
;; We have N positions in the P/R. You should provide two sets of
;; permutations P and reversal-bitmask R.
;; P is a permutation of (0 1 ... N-1). R is a list of N booleans
(define (make-permuter P0 P1 R0 R1)
(define regs (make-vector (length P0) #f))
(^[in-bit]
(set! (~ regs 0) in-bit)
(permute! regs (uncycle-perm (if in-bit P1 P0)))
(vector-map! (^[i b] (xor (~ (if in-bit R1 R0) i) b)) regs)
(~ regs 0)))
(define (make-encipherer P0 P1 R0 R1)
(define P (make-permuter P0 P1 R0 R1))
(define D #f)
(^[plaintext-input]
(^[] (glet1 in (plaintext-input)
(rlet1 r (xor in (P D))
(set! D r))))))
(define (make-decipherer P0 P1 R0 R1)
(define P (make-permuter P0 P1 R0 R1))
(define D #f)
(^[ciphered-input]
(^[] (glet1 in (ciphered-input)
(rlet1 r (xor in (P D))
(set! D in))))))
(define (xor a b) (if (and a b) #f (or a b)))
;; Convert cycle notation of permutation (see TAOCP 1.3.3) into the
;; second-line of the two-line permutation.
(define (uncycle-perm p)
(map cdr (sort-by (map cons p (append (cdr p) p)) car)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment