Rail Fence Cipher

I am currently trying to implement the rail fence cipher (Rail fence cipher - Wikipedia) in Clojure. I have to implement two functions encrypt and decrypt that take two parameters - string to encrypt/decrypt and number of rails (row). The solution must be as functional as possible (no loop recur etc.). I would be very thankful for any help because I dont even know where to start.

it’s going to be slow if you use the functional style. try wrapping this:

Happy new year! :partying_face:
I had a stab at a pure clojure implementation, using the wikipedia page. Its a fast and dirty solution.

;;; railfence 'encryption'

(def message "WE ARE DISCOVERED. RUN AT ONCE")
(require '[clojure.string :as str])
(defn railfence-ciphertext [message]
  (let [message (str/replace message #"\W" "")
        rails
        (for [[start skip] [[0 4] [1 2] [2 4]]]
          (apply str (take-nth skip (drop start message))))]
    (apply str rails)))
(railfence-ciphertext message)
;; => "WECRUOERDSOEERNTNEAIVDAC"


(defn railfence-decrypt [ciphertext]
  (let [n-rails 3
        k (-> (count ciphertext)
              (/ (* 2 (dec n-rails))))
        splitter (fn [s]
                   [(take k s)
                    (take (* 2 k) (drop k s))
                    (take k (drop (* 3 k) s))])
        [top middle bottom] (splitter ciphertext)]
    ;; not general, should be rewritten for arbitrary n-rails
    (loop [top top
           middle middle
           bottom bottom
           result (transient [])]
      (if (seq middle)
        (let [a (first top)
              b (first middle)
              c (first bottom)
              d (second middle)]
          (recur (rest top) (drop 2 middle) (rest bottom) (reduce conj! result [a b c d])))
        (apply str (persistent! result))))))

(railfence-decrypt (railfence-ciphertext message))
;; => "WEAREDISCOVEREDRUNATONCE"
1 Like

No loop/recur. Fairly “functional” (map, filter, reduce). Works for arbitrary # of rails.

;; remove whitespace
(defn rmws [s] (clojure.string/replace s #"\W" ""))

;; cycle of row indexes for a rail fence cipher
(defn fc-row-cycle [rails]
  (cycle (concat (range rails)
                 (reverse (drop-last (rest (range rails)))))))

;; Given sequence s of [char row] pairs, return a string of the chars in row n
(defn getrow [s n]
  (apply str (map first (filter (fn [[_ row]] (= n row)) s))))

(defn encrypt [msg rails]
  (->> (range rails)
       (map (partial getrow (map vector (rmws msg) (fc-row-cycle rails))))
       (clojure.string/join " ")))

@(def ct (encrypt "WE ARE DISCOVERED RUN AT ONCE" 3))
;; => "WECRUO ERDSOEERNTNE AIVDAC"

(defn rem1
  "Remove the first character of the string at index n and append
  it to acc. Return [<accumulated string> <updated-sequence>]"
  [[acc s] n]
  [(clojure.string/join [acc (first (get s n))])
   (update s n #(apply str (rest %)))])

(defn decrypt [ct rails]
  (->> (take (count (rmws ct)) (fc-row-cycle rails))
       (reduce rem1 ["" (clojure.string/split ct #" ")])
       first))

;; decrypt ciphertext ct using 3 rails.
(decrypt ct 3)
;; => "WEAREDISCOVEREDRUNATONCE"

Hi everyone, it’s my first interaction with the community.
I’ve done something recently I wanna share and please get me some feedbacks :slight_smile:
Thanks

;; encript
;W . . . E . . . C . . . R . . . U . . . O . . .
;. E . R . D . S . O . E . E . R . N . T . N . E
;. . A . . . I . . . V . . . D . . . A . . . C .
; WECRUO ERDSOEERNTNE AIVDAC

;; encript with spaces
;;WRIVDN EEAEDSOEE U TOC  CRRAN

;; decript
;;W E C R U O
;;ERDSOEERNTNE
;;A I V D A C

(defn- sanitize
  [text]
  (-> text
    (clojure.string/replace #"[\s]" "_")
    (clojure.string/replace #"[^A-Za-z_]" "")))

(defn- unsanitize
  [text]
  (-> text
    (clojure.string/replace #"[^A-Za-z_]" "")
    (clojure.string/replace #"[_]" " ")))

(defn- zigzag
  [text rails]
  (let [initial-data     {:rail      0
                          :direction :up
                          :fence     (vec (repeat rails []))}
        update-direction (fn [m r d] (merge m {:direction d
                                               :rail      (cond-> r
                                                            (= d :up) inc
                                                            (= d :down) dec)}))
        fence-builder    (fn [{:keys [rail direction] :as acc} curr]
                           (let [top?    (= rail (dec rails))
                                 bottom? (= rail 0)
                                 middle? (not (or top? bottom?))]
                             (cond-> acc
                               top? (update-direction rail :down)
                               bottom? (update-direction rail :up)
                               middle? (update-direction rail direction)
                               :always (update-in [:fence rail] #(conj % curr)))))]
    (reduce fence-builder initial-data text)))

(defn- gen-hash
  [{:keys [fence]}]
  (apply str (flatten fence)))

(defn encrypt
  [text rails]
  (-> text
    sanitize
    (zigzag rails)
    gen-hash))

(is (= "WRIVDN_EEAEDSOEE_U_TOC__CRRAN"
      (encrypt "WE ARE DISCOVERED. RUN AT ONCE" 3)))

(is (= "W_VR_EEDOE_UTO_RICRDNANEASE_C"
      (encrypt "WE ARE DISCOVERED. RUN AT ONCE" 4)))

(defn- build-zigzag
  [hash rails]
  (loop [fence (:fence (zigzag hash rails))
         hash  (vec hash)
         text  []]
    (if (empty? fence)
      text
      (let [size (count (first fence))]
        (recur
          (next fence)
          (vec (drop size hash))
          (conj text (subvec hash 0 size)))))))

(defn- fill-zigzag
  [fence text rails]
  (let [initial-data     {:rail      0
                          :direction :up
                          :fence     fence
                          :text      []}
        update-direction (fn [m r d] (merge m {:direction d
                                               :rail      (cond-> r
                                                            (= d :up) inc
                                                            (= d :down) dec)}))
        fence-builder    (fn [{:keys [rail direction] :as acc} _]
                           (let [top?    (= rail (dec rails))
                                 bottom? (= rail 0)
                                 middle? (not (or top? bottom?))]
                             (cond-> acc
                               top? (update-direction rail :down)
                               bottom? (update-direction rail :up)
                               middle? (update-direction rail direction)
                               :always (as-> $
                                         (update $ :text #(conj % (first (get-in $ [:fence rail]))))
                                         (update-in $ [:fence rail] #(next %))))))]
    (reduce fence-builder initial-data (range (count text)))))

(defn gen-text
  [{:keys [text]}]
  (apply str text))

(defn decrypt
  [hash rails]
  (-> hash
    (build-zigzag rails)
    (fill-zigzag hash rails)
    gen-text
    unsanitize))

(is (= "HELLO WORLD AGAIN"
      (decrypt "HORANEL_OL_GILWDA" 3)))

(is (= "WE ARE DISCOVERED RUN AT ONCE"
      (decrypt "WRIVDN_EEAEDSOEE_U_TOC__CRRAN" 3)))

(is (= "WE ARE DISCOVERED RUN AT ONCE"
      (decrypt "W_VR_EEDOE_UTO_RICRDNANEASE_C" 4)))

How did you reason about the fc-row-cycle indices ? That was really my blocker for making a general algo.

This was my thinking:

Look at the examples in Wikipedia. Make sure to use at least 4 rails so you have the “general case”. Annotate the examples with rail index of each letter. A pattern becomes obvious.

Looking at the pattern of “rail indexes”, it’s a cycle that repeats after going from top (index 0) to bottom (index n) and then back to one step before the top. Top to bottom is simply (range 0 n). Bottom to top is the reverse of that without index n or index 0, so (reverse (drop-last (rest (range n)))). This cycle repeats throughout the message (of unknown length) so we concat the “top to bottom” sequence with the “bottom to top” sequence and make it a lazy infinite cycle with “cycle”.

All of this is needed to we can find out which letters in the encrypted message are on which “rails”.

1 Like

Hi, I’ve been monitoring this interesting topic but didn’t find time to post. I appreciated how smart the solution from @mchampine was but it was the same for me with fc-row-cycle, the clojure functions obscured the math.

Here’s how I reasoned about at it. With the solution from @magnus0re, it’s clear the key part of the encryption algorithm is the for, specifically [0 4] [1 2] [2 4]. The rest is just working around that as the key to character translation. To generalize this version of the encryption algorithm, it seems like you can just generalize that exact part. I wrote out a few iterations for rails r and noticed noticed the pattern actually holds from r=0, or at least r=1.

Each 2-vector of [start skip] is simple. The first term, where each iteration of the letter grabber starts, like it was stated in different words elsewhere, is (range r). The second term only needs one number each for r≤3, but for r>3, the amount of letters that are skipped alternate when counting rows in sequence. The pattern (the way I’m stating it isn’t mathematically sound) of the first term of skip m begins at 2(r-1) and decrements by two until m=0. That list is reversed and paired with the same terms. Then, for the cipher to work, the zeroes are dropped from the first and last terms, excepting r=1.

I had some success implementing the solution from @magnus0re the same way, but using a vector with cycle for the skip value, taking the nth term using start made with range.

If that isn’t well stated, or my explanation has holes in it lmk.