違法素数がちょっと話題になったことがあります。

まさに天才的発想...違法プログラムを素数に変換した「違法素数」が話題に - Togetterまとめ

どういう仕組みなのかはWikipediaのページを読めば書いてあるし、せっかくだから自分で違法素数形式の素数を作ってみたいなーと思いました。

元ネタの違法素数は「Gzipファイルの末尾に不要なバイナリが付いていても無視される」ということを上手く利用しています。私がやってみたいのは プレインテキストを素数化して、デコードすると元テキストが表示される というもの。さらにひと工夫してハンドルネーム（deltam）をきれいに素数化できないか試してみます。

準備

まず違法素数形式のデコードをするプログラムを書きます。
（Clojureで書いたけど他の言語でもできます）

decode.clj

;;; Usage: cat illegal_prime.txt | clj decode.clj > decss.c.gz
;;;        gunzip decss.c.gz

(def txt (read-line))
(def illegal-prime (bigint (clojure.string/replace txt #"[^0-9]" "")))
(def prime-bytes (.toByteArray (.toBigInteger illegal-prime)))

(def stdout (.getChannel (java.io.FileOutputStream. java.io.FileDescriptor/out)))
(.write stdout (java.nio.ByteBuffer/wrap prime-bytes))

では肩慣らしにWikipediaにある違法素数をデコードしてみましょう。
違法素数をコピペしてillegal_prime.txtに保存しておきます。

$ cat illegal_prime.txt | clj decode.clj > decss.c.gz
$ gunzip decss.c.gz

gzip: decss.gz: decompression OK, trailing garbage ignored
$ head decss.c
void CSSdescramble(unsigned char *sec,unsigned char *key)
{
        unsigned int t1,t2,t3,t4,t5,t6;
        unsigned char *end=sec+0x800;

        t1=key[0]^sec[0x54]|0x100;
        t2=key[1]^sec[0x55];
        t3=(*((unsigned int *)(key+2)))^(*((unsigned int *)(sec+0x56)));
        t4=t3&7;
        t3=t3*2+8-t4;

おっとこれ以上表示するとデジタルミレニアム著作権法に引っかかってしまう。

これで違法素数のデコードのやり方が分かりました。

バイト列を素数にする

違法素数形式でバイト列を素数化する方法はざっくり書くとこんな感じ。

バイト列をビッグエンディアンで一つの巨大整数にする（1バイト目が最上位になるやつ）
巨大整数を素数判定する
素数なら終了
合成数なら256を掛けた数字に、1から255までの数字を足してみてまた素数判定する
- 巨大整数*256 + 1, 巨大整数*256 + 3, … , 巨大整数*256 + 255
- 最下位バイトが偶数なら偶数になってしまうから奇数だけ試せばOK
  - 実は巨大整数と互いに素な数字のみ試せばOK
ここまで試してもだめなら0x10000を掛けて0xFFFFまで足し算して試す。
以下、同様に探索を続ける

幾つか疑問点が出てきます。

なんで256を掛けるの？
- 8ビットシフトの意味。そうすると255までの足し算は末尾に不要バイトを付け足すという意味になる。
この探索を続けても素数が見つからない場合もあるんじゃないの？
- 素数が存在することを保証してくれる算術級数定理というのがある。
  - ”互いに素である自然数a,bに対して、an+b（nは自然数）と書ける素数が無限に存在する”
- a=巨大整数（コード化するビット列）、b=末尾の不要バイト列、n＝256の累乗（何回かの8ビットシフト）と考えればいつか素数が見つかりそう。

探索

上記の手順使ってREPLで探索してみますが、その前によく使う関数を定義しときます。

(defn gcd
  "最大公約数を返す"
  [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))

(defn coprime?
   "互いに素か？"
  [a b]
  (= 1 (gcd a b)))

(defn prime?
  "素数か？"
  [n]
  (loop [i 2]
    (if (< n (* i i))
      true
      (if (= 0 (mod n i))
        false
        (recur (inc i))))))

(defn find-prime-seq
  "素数の候補シーケンスを返す"
  [data offset]
  (map #(+ (* data offset) %)
    (filter #(coprime? % data)
      (range 2 offset))))

まずdeltamを整数化します
（最終的な値の範囲が分からないので念のためBigIntegerにしています）

(defn str->bigint
  "文字列を整数化する"
  [s]
  (reduce #(+ (* %1 256) %2)
    (map #(bigint (int (char %))) s)))

; => (str->bigint "deltam")
; 110386774040941N

この110386774040941は素数ではないです。

110386774040941 - Wolfram|Alpha
101×113×36527×264791

ではこれから素数を探索してみます。

repl

=> (def nums (find-prime-seq 110386774040941N 256))
=> (first (filter prime? nums))
28259014154481059N

28259014154481059ができました。WolframAlphaで検索してみるとちゃんと素数！

28259014154481059 - Wolfram|Alpha
28259014154481059 is a prime number.

では復号してみます。

$ echo 28259014154481059 | clj decode.clj ; echo # 見やすいように改行させる
deltam�

できました！

ひと工夫

これでプレインテキストを素数化することができました。ですが末尾の不要バイトが表示するときに目障りですね。なんとかこれを表示しないようには出来ないでしょうか？

不要バイトといえどASCIIコードのどれかなので、末尾に追加するバイトに制限を設けて再度探索すればどうでしょう。つまりASCIIの 非表示の制御文字 を使います。

ASCII - Wikipedia

末尾に付け足すバイトの範囲を制御文字に制限するため、ちょっと改造します。

(defn tail-bytes
  "末尾に追加するバイトの候補列を返す"
  [offset]
  (let [ascii-control-chars (cons 127 (range 32))]
    (if (<= offset 256)
      ascii-control-chars
      (for [a ascii-control-chars, b (tail-bytes (int (/ offset 256)))]
        (+ (* 256 b) a)))))

(defn find-prime-seq
  "素数の候補シーケンスを返す"
  [data offset]
  (map #(+ (* data offset) %)
    (filter #(coprime? % data)
      (tail-bytes offset ))))

これでまた探索を実行

REPL

=> (def nums (find-prime-seq 110386774040941N 256))
#'user/nums
=> (time (first (filter prime? nums)))
"Elapsed time: 10247.025955 msecs"
nil

探索範囲には素数が無いみたいなので16ビットシフトしてまた試してみます。

REPL

=> (def nums (find-prime-seq 110386774040941N (* 256 256)))
#'user/nums
=> (time (first (filter prime? nums)))
"Elapsed time: 500902.099991 msecs"
7234307623547111039N

見つかったので素数かどうか確認。

7234307623547111039 - Wolfram|Alpha
7234307623547111039 is a prime number.

復号してみる。

decode

$ echo 7234307623547111039 | clj decode.clj ; echo # 見やすいように改行させる
deltam
$ echo 7234307623547111039 | clj decode.clj | od -a -t d1
0000000    d   e   l   t   a   m ack del
          100 101 108 116  97 109   6 127
0000010

できました！

まとめ

違法素数形式でプレインテキストを素数化しました
ASCII制御文字を使うことで復号したときに目当てのテキスト以外が目立たないように工夫しました
ハンドルネームをいい感じに素数化できて満足

おわり。

「違法素数」形式でハンドルネームをいい感じに素数化してみる

準備

バイト列を素数にする

探索

ひと工夫

まとめ