arc の日記

はてなダイアリーから引っ越してきました。さらに新しい記事は https://junkato.jp/ja/blog/ で書いています。

情報理工学系研究科の入試案内ポスターにまつわる話

university

Share photos on twitter with Twitpic
これ、情報理工学系研究科入試案内のポスターです。最初は妖しい和装の女の子が話題になりましたが、よく見てみると薄く0と1の羅列が載ってます。また、情報理工学系の教授が数か月前に「意味のある0と1からなる数列{0,1}*」を募集していたことが分かりました。
そこで、この羅列に意味があるんじゃないかという話になり、先ほどTwitterで解読祭りが開かれました。様子はTwitterのハッシュタグ#istcryptographyを見ると分かります。
結論から言えば、そこまで大したものが出てきたわけじゃなかったし、そもそも教授の発言とポスターの関係もはっきりしないんですが、問題としてはちょっとヒネりがあってGW中のいい暇つぶしになったので、答え合わせをしておきます。

解読に至った経緯

まず、@plus7氏がポスターの字を書き起こしてブログにポストしました。これが一番すごい労力…お疲れ様でした。
そして、書き起こしを@shun_no_suke氏が画像としてデコードするなどして、だいたい何かの繰り返しになっていることが分かってきました。
Posted using Mobypicture.com
画像中にλのような記号が見えたりして盛り上がりますが、その後しばらくして、繰り返しが意味しているものがあっけなく分かります。

http://twitter.com/shitijyou/status/13185236653

何のことはない、基本的にはアスキーコードを2進法表記したものの繰り返しでした。

実はヒネってあった問題

調べてみると分かるのですが、繰り返しは623文字ごと（623bit）です。

Looking for repetition in the question binary.
	Original seed: 100011101110010011000010110010...
	Second appearance of the seed: 623
	Third appearance of the seed: 1246

アスキーコードは1字8bitなので、8で割り切れないのはおかしいです。実は、繰り返しの先頭に一字「0」を加えると正しく「Graduate School of Information Science and Technology, The University of Tokyo」に復号されるようになっていました。
この暗号を作ったのが誰かは分かりませんが、解く道筋としては

  1. 普通にアスキーコードとして復号しようとしても文字化けしてしまう
  2. 繰り返しを発見
  3. 繰り返し単位数が半端なことに気付く
  4. アスキーコードは0でしか始まらないのに繰り返しが1で始まっているので試しに0をつけてみる
  5. 繰り返し単位数が8の倍数になるうえ、ちゃんと復号される！

といったものを想定していたかもしれません。
しかし、実際には1.の時点で答えがだいたい分かってしまいました。

味わい深いところ

今回の件で味わい深いのは、もしポスターの文字列を正しく写せていたら1.の時点では答えが分からなかったことです。
すなわち、先頭の1bitが足りないアスキーコード列の先頭がエンコーディングにうまく合うには繰り返しが最低7回必要ですが、問題の文字列自体は3000字程度で繰り返しが高々4回なので、1.の時点では文字がうまく復号されないはずだったのです。
試しに手写しの文字列と「正しく写せていたらこうなっていたはず」の文字列を重ね合わせてみるとこうなります。

下のほうがボコボコになっていますね。確かめていませんが、その辺で文字が抜けたか余計に足されてしまっているように見えます。（逆に言えば、それ以外全部正しく写している@plus7氏、すごいです。）
つまり、人的なミスのためにかえって暗号解読が捗った可能性があるわけで、面白いなーと思いました。

以下、検証用のJavaソースコードが続きます。

import java.awt.AlphaComposite;
import java.awt.Color;
import java.awt.Composite;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.awt.image.WritableRaster;

import javax.swing.JFrame;
import javax.swing.JPanel;

/**
 * 情報理工系研究科の入試案内のやつ
 */
public class ISBinaryString {

	public static void main(String[] args) {

		// 問題( @plus7 氏の手写し)
		String questionBinary = "1000111011100100110000101100100011101010110000101110100011001010010000001010011011000110110100001101111011011110110110000100000011011110110011000100000010010010110111001100110011011110111001001101101011000010111010001101001011011110110111000100000010100110110001101101001011001010110111001100011011001010010000001100001011011100110010000100000010101000110010101100011011010000110111001101111011011000110111101100111011110010010110000100000010101000110100001100101001000000101010101?011100110100101110110011001010111001001110011011010010111010001111001001000000110111101100110001000000101010001101111011010110111100101101111100011101110010011000010110010001110101011000010111010001100101001000000101001101100011011010000110111101101111011011000010000001101111011001100010000001001001011011100110011001101111011100100110110101100001011101000110100101101111011011100010000001010011011000110110100101100101011011100110001101100101001000000110000101101110011001000010000001010100011001010110001101101000011011100110111101101100011011110110011101111001001011000010000001010100011010000110010100100000010101010110111001101001011101100110010101110010011100110110100101110100011110010010000001101111011001100010000001010100011011110110101101111001011011111000111011100100110000101100100011101010110000101110100011001010010000001010011011000110110100001101111011011110110110000100000011011110110011000100000010010010110111001100110011011110111001001101101011000010111010001101001011011110110111000100000010100110110001101101001011001010110111001100011011001010010000001100001011011100110010000100000010101000110010101100011011010000110111001101111011011000110111101100111011110010010110000100000010101000110100001100101001000000101010101101110011010010111011001100101011100100111001101101001011101000111100100100000011011110110011000100000010101000110111101101011011110010110111110001110111001001100001011001000111010101100001011101000110010100100000010100110110001101101000011011110110111101101100001000000110111101100110001000000100100101101110011001100110111101110010011011010110000101110100011010010110111101101110001000000101001101100011011010010110010101101110011000110110010100100000011000010110111001100100001000000101010001100101011000110110100001101110011011110110110001101111011001110111100100101100001000000101010001101000011001010010000001010101011011100110100101110110011001010111001001110011011010010111010001111001001000000110111101100110001000000101010001101111011010001110111001001100001011001000111010101100001011101000110010100100000010100110110001101101000011011110110111101101100001000000110111101100110001000000100100101101110011001100110111101110010011011010110000101110100011010010110111101101110001000000101001101100011011010010110010101101110011000110110010100100000011000010110111001100100001000000101010001100101011000110110100001101110011011110110110001101111011001110111100100101100001000000101010001101000011001010010000001010101011011100110100101110110011001010111001001110011011";
		String answerCandidateBinary = lookForRepetition(questionBinary);

		// 答え
		String answerUnit = "Graduate School of Information Science and Technology, The University of Tokyo";
		StringBuffer buffer = new StringBuffer();
		byte[] bs = answerUnit.getBytes();
		for (final byte b : bs) {
			int bi = (int) b;
			for (int i = 7; i >= 0; i--) {
				buffer.append(bi >> i & 1);
			}
		}
		String answerUnitBinary = buffer.toString();
		String answerUnitBinaryWithout1st1bit = answerUnitBinary.substring(1);

		// 合ってる？
		System.out.print("Checking if the answer candidate equals the real answer: ");
		System.out.println(answerCandidateBinary
				.equals(answerUnitBinaryWithout1st1bit) ? "OK" : "NG");

		// ちなみに、問題の写し間違え具合を調べてみると…
		buffer.delete(0, buffer.length());
		while (true) {
			if (buffer.length() + answerUnitBinaryWithout1st1bit.length() < questionBinary
					.length()) {
				buffer.append(answerUnitBinaryWithout1st1bit);
			} else {
				buffer.append(answerUnitBinaryWithout1st1bit.substring(0,
						questionBinary.length()
								% answerUnitBinaryWithout1st1bit.length()));
				break;
			}
		}
		String answerBinaryForComparison = buffer.toString();
		compareAsImages(questionBinary, answerBinaryForComparison, 50, 3);
	}

	/**
	 * 文字列が繰り返している前提で、繰り返し単位を探す。
	 *
	 * @param str
	 * @return
	 */
	private static String lookForRepetition(String str) {
		System.out.println("Looking for repetition in the question binary.");

		// 先頭を適当な長さぶん切り出す
		String orig = str.substring(0, 30);
		System.out.println("\tOriginal seed: " + orig  + "...");

		// 二回目の出現箇所を探す: 623
		int second = str.indexOf(orig, orig.length());
		System.out.println("\tSecond appearance of the seed: " + second);

		// 念のため三回目の出現箇所を探す: 1246
		int third = str.indexOf(orig, second + 1);
		System.out.println("\tThird appearance of the seed: " + third);

		// (手動で調べてみたら一回目の繰り返しの中に ? があったので、)
		// 二回目のところを切り出して繰り返し単位として返す
		return str.substring(second, third);
	}

	/**
	 * 二つの文字列を画像化して比較表示する。
	 *
	 * @param aBinary
	 * @param bBinary
	 * @param width
	 * @param zoom
	 */
	private static void compareAsImages(String aBinary, String bBinary,
			final int width, final int zoom) {
		final BufferedImage questionImage = getImageRepresentation(aBinary,
				width);
		final BufferedImage answerImage = getImageRepresentation(bBinary, width);
		final int h = questionImage.getHeight();
		JFrame frame = new JFrame();
		JPanel panel = new JPanel() {
			private static final long serialVersionUID = 1L;

			@Override
			public void paintComponent(Graphics g) {
				super.paintComponent(g);
				g.setColor(Color.white);
				g.fillRect(0, 0, getWidth(), getHeight());
				g.setColor(Color.black);

				// 比較元の二つを表示する
				g.drawImage(questionImage, 5, 5, width * zoom, h * zoom, null);
				g.drawImage(answerImage, 10 + width * zoom, 5, width * zoom, h
						* zoom, null);

				// 二つを重ね合わせて表示する
				Graphics2D g2 = (Graphics2D) g;
				Composite comp = g2.getComposite();
				g2.drawImage(questionImage, 15 + width * zoom * 2, 5, width
						* zoom, h * zoom, null);
				g2.setComposite(AlphaComposite.DstAtop);
				g2.drawImage(answerImage, 15 + width * zoom * 2, 5, width
						* zoom, h * zoom, null);
				g2.setComposite(comp);
			}
		};
		panel.setPreferredSize(new Dimension(20 + width * zoom * 3, 10 + h
				* zoom));
		frame.add(panel);
		frame.pack();
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setVisible(true);
	}

	/**
	 * 0と1の繰り返す文字列を指定した幅で画像化して返す
	 *
	 * @param binStr
	 * @param width
	 * @return
	 */
	private static BufferedImage getImageRepresentation(String binStr, int width) {
		int length = binStr.length();
		int height = length / width;
		int[] bin = new int[length];
		for (int i = 0; i < length; i++) {
			bin[i] = binStr.charAt(i) == '1' ? 0xff000000 : 0;
		}
		BufferedImage image = new BufferedImage(width, height,
				BufferedImage.TYPE_INT_ARGB);
		WritableRaster raster = image.getRaster();
		raster.setDataElements(0, 0, width, height, bin);
		return image;
	}
}