146 lines
5.9 KiB
Common Lisp
146 lines
5.9 KiB
Common Lisp
;; shift-affine.lisp - Some simple subroutines for working with affine and shift
|
|
;; ciphers.
|
|
;;
|
|
;; This file is free software under the terms of the GPL3 license. You can find
|
|
;; a copy of the license at: https://www.gnu.org/licenses/gpl-3.0.en.html
|
|
|
|
(defpackage shift-affine
|
|
(:use :cl)
|
|
(:export
|
|
:char-letter :letter-char :affine-encrypt :extended-gcd
|
|
:modular-multiplicative-inverse :affine-encrypt :affine-decrypt
|
|
:shift-encrypt :shift-decrypt :*english-letter-frequencies*
|
|
:relative-frequencies :chi-squared :count-letters :shift-guess-key
|
|
:shift-try-break))
|
|
|
|
(in-package shift-affine)
|
|
|
|
(defun char-letter (char)
|
|
"Return the index of CHAR in the alphabet. The returned number is 0 for A, 1
|
|
for B, 2 for C, etc. Note that this will return the save value for upper and
|
|
lower case letters."
|
|
(- (char-code char)
|
|
(if (upper-case-p char)
|
|
(char-code #\A)
|
|
(char-code #\a))))
|
|
|
|
(defun letter-char (letter)
|
|
"Return the Lisp character object for LETTER. Letter should be the index of a
|
|
letter in the alphabet. For example, 0 for A, 1 for B, 2 for C, etc."
|
|
(code-char (+ letter (char-code #\A))))
|
|
|
|
(defun affine-encrypt (plain coef offset)
|
|
"Encrypt PLAIN using an affine encryption algorithm. COEF cannot be coprime
|
|
with 26. That is, it cannot be a multiple of 2 or 13. The algorithm used is:
|
|
f(p) = (COEF * p + OFFSET) mod 26
|
|
where this function is used to transform every letter of PLAIN."
|
|
(when (or (zerop (mod coef 2))
|
|
(zerop (mod coef 13)))
|
|
(error
|
|
"COEF must be coprime with 26 (not divisible by 2 or 13), but it was ~d"
|
|
coef))
|
|
(map 'string (lambda (char)
|
|
(if (alpha-char-p char)
|
|
(let ((letter (char-letter char)))
|
|
(letter-char
|
|
(mod (+ (* coef letter) offset) 26)))
|
|
char))
|
|
plain))
|
|
|
|
(defun extended-gcd (n1 n2)
|
|
"Return the greatest common denominator of N1 and N2. As a second value,
|
|
return a cons of (x . y) such char x * N1 + y * N2 = GCD."
|
|
(if (zerop n1)
|
|
(values n2 (cons 0 1))
|
|
(multiple-value-bind (div rem) (floor n2 n1)
|
|
(destructuring-bind (gcd (x . y))
|
|
(multiple-value-list (extended-gcd rem n1))
|
|
(values gcd (cons (- y (* div x)) x))))))
|
|
|
|
(defun modular-multiplicative-inverse (n m)
|
|
"Find the modular multiplicative inverse of N with respect to M. That is, some
|
|
integer i such that (N * i) mod M = 1."
|
|
(destructuring-bind (gcd (x . y))
|
|
(multiple-value-list (extended-gcd (if (minusp n)
|
|
(+ m n)
|
|
n)
|
|
m))
|
|
(declare (ignorable y))
|
|
(unless (= 1 gcd)
|
|
(error "N and M must be coprime. N: ~d, M: ~d" n m))
|
|
(+ x m)))
|
|
|
|
(defun affine-decrypt (cipher coef offset)
|
|
"Decrypt CIPHER, which should be a string encrypted by `affine-encrypt'. COEF
|
|
and OFFSET should be the same as the values passed when encrypting CIPHER."
|
|
(let ((ic (modular-multiplicative-inverse coef 26)))
|
|
(affine-encrypt cipher ic (- (* offset ic)))))
|
|
|
|
(defun shift-encrypt (plain offset)
|
|
"Encrypt PLAIN by shifting each letter by OFFSET."
|
|
(affine-encrypt plain 1 offset))
|
|
|
|
(defun shift-decrypt (cipher offset)
|
|
"Decrypt CIPHER by shifting each letter by -1 * OFFSET."
|
|
(affine-encrypt cipher 1 (- offset)))
|
|
|
|
(defparameter *english-letter-frequencies*
|
|
#(8.2 1.5 2.8 4.3 12.7 2.2 2.0 6.1 7.0 0.15 0.77 4.0 2.4 6.7 7.5 1.9 0.095 6.0
|
|
6.3 9.1 2.8 0.98 2.4 0.15 2.0 0.074)
|
|
"Percent frequency of each letter of the English alphabet in standard writing.
|
|
Source: https://en.wikipedia.org/wiki/Letter_frequency")
|
|
|
|
(defun relative-frequencies (seq)
|
|
"Find the relative percent frequency of the sample data in SEQ."
|
|
(let ((sample-count (reduce '+ seq)))
|
|
(map 'vector (lambda (elem)
|
|
(/ elem sample-count))
|
|
seq)))
|
|
|
|
(defun chi-squared (data ref-data &key (offset 0))
|
|
"Return the sum of the square of the error between each index of DATA and
|
|
REF-DATA. Before performing the calculation, shift each element in DATA by
|
|
OFFSET indexes, wrapping. That is, with OFFSET 1, index 0 becomes index 1, and
|
|
the last index becomes index 0."
|
|
(loop for ref across ref-data
|
|
for i upfrom offset
|
|
for sample = (aref data (mod i (length data)))
|
|
summing (/ (expt (- sample ref) 2) ref)))
|
|
|
|
(defun count-letters (str)
|
|
"Count the number of times each letter appears in STR. Return a vector with
|
|
each index being the number of times that letter appeared."
|
|
(loop with freq-data = (make-array '(26) :initial-element 0)
|
|
for char across str
|
|
for letter = (char-letter char)
|
|
when (alpha-char-p char)
|
|
do (incf (aref freq-data letter))
|
|
finally (return freq-data)))
|
|
|
|
(defun shift-guess-key (cipher &key (reference *english-letter-frequencies*))
|
|
"Try to guess the shift offset for CIPHER. This is done by analyzing the
|
|
frequencies of letters in CIPHER and finding the shift offset that most closely
|
|
matches those listed in REFERENCE, which defaults to `*english-letter-frequencies*'."
|
|
;; We also try CIPHER as is, just in case
|
|
(let ((best-chi-squared most-positive-fixnum)
|
|
(best-offset 0)
|
|
(freq-data (relative-frequencies (count-letters cipher))))
|
|
(dotimes (i (length reference) best-offset)
|
|
(let ((chi-squared (chi-squared freq-data reference
|
|
:offset i)))
|
|
(when (< chi-squared best-chi-squared)
|
|
(setq best-chi-squared chi-squared
|
|
best-offset i))))))
|
|
|
|
(defun shift-try-break (cipher &key (reference *english-letter-frequencies*))
|
|
"Attempt to decrypt CIPHER by guessing the shift offset. This uses
|
|
`shift-guess-key' (which see) internally. REFERENCE is passed verbatim to
|
|
`shift-guess-key'. As a second value, return the key used for decryption."
|
|
(let ((key (shift-guess-key cipher :reference reference)))
|
|
(values (shift-decrypt cipher key)
|
|
key)))
|
|
|
|
;; Local Variables:
|
|
;; jinx-local-words: "coprime"
|
|
;; End:
|