FSAngo解読｜富士ソフト株式会社

FSAngo解読

FSAngo解読コンテストに多数のご参加頂きありがとうございました。FSAngo解読コンテストの暗号解読結果を発表致します。

懸賞問題

●

出題

下記に示す暗号文 (ciphertext) に対応する以下の項目を解答して下さい。

1.	平文（Plaintext)
2.	乱数の初期値 x0 （Inital value)
3.	R暗号化開始時のアファイン鍵 (Affine Key)

77 17 15 1d a2 70 8c 82 59 e8 53 7c 18 32 77 fc bf 7e 0e dd
57 b4 52 f5 79 30 69 2c 74 7b de cd 6b b8 60 76 78 5e 0b a1 
09 d5 5b 82 a3 4f a7 3d e9 ed 13 7e a7 1b 66 a8 33 de 5e 5d 
37 7d 1f eb 46 87 5c ee 09 f9 6b 12 e3 12 17 a4 38 8b d4 68 
8e ea 82 9e 55 a3 16 a5 23 7e 98 70 42 a3 41 56 70 27 32 1f 
12 27 58 d2 a5 a6 b3 e2 35 38 1d b3 a7 6f c5 d7 9e 72 ac 01 
40 30 3c 3b b9 26 64 20 a1 5f 1a b9 2e e0 b4 a4 4a a5 7e 96 
1e 59 62 18 8f ef 70 15 8c 15 b3 b2 79 b8 a8 3c 40 27 68 e6 
dd 3e 2d 7a 10 e7 26 7d f5 ae 9e 99 28 eb 37 dd 0d 48 04 ba 
f9 7a 7e 7c bd 25 4d 78 32 cb 4c e2 f9 41 40 10 b9 09 fa 3b 
a0 64 9e c5 e7 0f cc 38 d8 c1 84 2c 37 e3 15 e9 33 3a e0 bb 
09 5c 7c a4 c9 67 35 18 cc 1b fd 5f 75 89 b5 8e e5 24 ce 37 
15 b4 36 16 ee 62 32 2f 21 58 d0 af e8 e9 3b e8 7b 15 7b 79 
0b 72 db 5c c9 6a 34 0d 36 62 85 12 6f c4 84 e0 24 c7 98 76 
23 4b 35 57 41 99 a3 a1 b6 01 1b 90 1c 58 e5 20 3b af 6a 7e 
46 ea 8a cc d8 52 82 dc b3 cf f0 d4 27 df 2d 18 ca ff a2 5d 
da ad d3 b2 38 8f 1a df bc 08 cd 9e de 5b aa ed fa 18 4f c9 
24 1c 29 18 16 d6 a6 13 a0 7e 28 f9 f3 f1 58 10 48 6a e4 4e 
37 de 62 f3 6e 90 00 41 a2 fd b1 bf 44 98 89 39 33 80 87 4a 
48 0a 28 f9 cf 01 6a 3f 06 50 11 a4 c0 4b ca 1a d5 0a dc 70 
4e 4f d0 63 4a e2 14 10 ad 6a 19 be 9e db 21 e2 b8 e1 93 30 
87 31 0c 0d 70 62 6c 71 5a 38 f3 79 17 ba 85 86 30 2c 8a 5f 
52 46 0a bd 29 c7 7e 4c 02 d8 12 ed 1a 55 b4 8d 88 33 1e e4 
7f b8 94 97 13 5e bc 3d 45 ab 22 58 3a f1 dc 75 de ea bf e7 
bc b7 0d 71 85 23 d6 1d a0 49 62 6d 45 8a df b7 27 9b 36 bd 
d6 88 43 f5 bb bb f8 49 02 a0 a6 15 39 0a a4 70 06 ce a9 46 
db 0b 5d 57 8b fe 64 b8 12 2e d3 0b 56 b8 fe dd ee ab d4 32 
db 11 be a7 bd 07 0c 52 69 4e 1d 9e 93 cf 8a 16 7d 6c b5 a6 
5f a5 50 8f e5 ae 60 50 03 1a e6 bc 1a c1 8a f5 f3 21 53 3e 
6a 85 32 f5 9e 70 08 17 40 d7 8f b4 d5 d2 cd 6f 86 eb 72 62 
5c 5f 27 d8 85 c3 17 6a 9a 62 a1 21 2f e7 04 c9 f1 d6 8c ee 
af 63 b1 3d 9a d3 5f 3e 21 a5 a3 e3 ab b3 08 17 0d 41 d8 4d 
04 ca ac 7e bf f9 6d 86 16 92 27 7d 83 57 ae dc c0 3b 78 66 
92 5c 6f 05 38 2b cc 2c a4 63 89 9e 94 0a d4 68 fa 8b d3 4e 
2b b8 0a 47 45 d5 06 68 b4 f3 4c c1 4c f4 69 71 3a 11 fd d7 
70 ce 75 b1 68 f8 bf 7d 62 a4 e5 89 79 0c 47 59 62 93 d3 04 
c4 e1 aa 54 0f 81 b2 07 96 32 bf e3 f3 3f 33 25 f5 f4 00 18 
6a 97 be b0 81 82 a1 7d e3 81 2d ed a4 d8 b8 c6 cf 25 9a 75 
78 ed 5a be d1 f7 0a 7c 7c 4a 20 1f a9 bf d8 a7 b8 4e 32 05 
ab aa 37 56 07 32 f0 fd 6d 8e e6 e2 34 af 4e 85 99 74 74 f0 
57 3d d6 42 c4 e2 0f e7 30 f5 24 0b b1 2a 40 6a 9a d0 46 95 
53 3e 32 05 bd ec 40 5f 35 f2 f5 82 8d 0f 6e 1f 05 99 e6 a9 
0f b9 53 c4 16 e1 9b 85 62 cd f5 be 80 19 30 c7 fc 5b 64 7a 
12 0b ff 7b 6d f9 d2 94 6c 18 66 6f 4f d1 68 eb f2 c9 38 2d 
23 1c 44 12 ab b4 2c c0 3e 76 fa 49 99 74 35 5b 61 8c 5e 9f 
71 9f c4 dd e6 47 6c e2

●

解読

平分

It is rather for us to be here dedicated to the great task remaining b efore us--that from these honored dead we take increases devotion to t hat cause for which they gave the last full measure of devotion--and t hat goverment of the people, by the people, for the peaple, shall not perish from the earth. In the beginning God created the heaven and th e earth. And the earth was with out form, and void; and darkness was upon the face of the deep, & the spirit of god moved upon the face of the waters. The sun of the kinetic and rest energy of an object: E=m* (c**2)*r. The amount of rest energy in an object: E=m*(c**2). r is g amma factor: 1/sqrt(1-(v**2/c**2)). v is the victory of the object we 're talking about, while c is the speed of right. O Caesar, Hence! W ilt thou lift up Olympus? Great Caesar, -- Doth not Brutus bootless k neel? Speak, hands forme! ..... Et tu, Brute! Then fall, Caesar.

なお、上記平文には改行コードは含まれません。

初期値 x0（１６進数）

4fb5

なお、上記平文には改行コードは含まれません。

アファイン鍵(16進数)

アファイン鍵	係数 a	係数 b	アファイン鍵	係数 a	係数 b
K[0]	5666	bc20	K[32]	987c	0714
K[1]	6c55	13ce	K[33]	9bb7	4d1d
K[2]	6b70	0ea5	K[34]	6b82	4e33
K[3]	9b82	86b8	K[35]	e157	65f6
K[4]	5dc8	037e	K[36]	0a11	7031
K[5]	7d40	fedc	K[37]	5993	5fb4
K[6]	8916	a85e	K[38]	5087	9cf6
K[7]	83d4	c776	K[39]	1760	e5ee
K[8]	3ac1	5632	K[40]	b798	567f
K[9]	986e	ff03	K[41]	038b	e7b6
K[10]	2d4c	ec86	K[42]	2e51	7b2f
K[11]	b7c2	00a4	K[43]	9d5a	61de
K[12]	9eaa	8d37	K[44]	e169	1c94
K[13]	89de	8665	K[45]	6e14	ca00
K[14]	ea9d	caf3	K[46]	8443	56dd
K[15]	7543	3250	K[47]	8077	2efe
K[16]	c593	71d1	K[48]	3e32	5b82
K[17]	5345	cd3c	K[49]	a7cc	397b
K[18]	7d29	c130	K[50]	5a71	8282
K[19]	56d5	3ab6	K[51]	9115	f44d
K[20]	48c7	1ed2	K[52]	651a	e799
K[21]	d0aa	e5d6	K[53]	0417	3b46
K[22]	975b	62fb	K[54]	a745	3337
K[23]	7f0a	93dc	K[55]	8526	cea6
K[24]	48fc	886a	K[56]	bb35	e92f
K[25]	7b25	78f4	K[57]	1d68	a2bc
K[26]	298a	87ac	K[58]	cd68	6bf2
K[27]	0363	b078	K[59]	4f25	0424
K[28]	1b4b	d235	K[60]	358e	3a40
K[29]	5859	338d	K[61]	523b	a851
K[30]	d547	d870	K[62]	5105	1616
K[31]	1243	ea1c	K[63]	5e42	f614

●

解説

ここで使用する数値は全て正の整数とし、アファイン鍵の添え字 i, j を除き全て１６進数で表示します。

FSAngoは乱数生成器（FSRansu）で生成られた擬似乱数列を使用して暗号化／復号化を行います。ここでは始めに FSRansu による乱数生成方法を解説し、ここで生成された擬似乱数列を用いた暗号化／復号化方法を示します。

FSRansu による擬似乱数生成方法
アファイン鍵数を M、a, b, c，n を要素とする各アファイン鍵を K[i] (i＝0,..,M-1) で表します。ここで a, b はアファイン鍵の係数、c はそのアファイン鍵の使用回数、n はそのアファイン鍵の寿命とします。

擬似乱数列 { Xk } の生成は

1.	k = 1, i = 0
2.	Xk = ( K[i].a * X(k-1) + K[i].b ) (and) 7FFF
3.	K[i].c = K[i].c + 1
4.	j = ( Xk (shr) 8 ) (mod) M
5.	if ( K[i].c >= K[i].n ) then w(i, j)
6.	i = j, k = k + 1
7.	goto 2.

の通りです。ここで演算子 (and)、(mod) はビット毎の論理積演算、剰余演算を、(shr) は右シフト演算を表します。

また、w(i, j) は第ｉ番目のアファイン鍵をｊをパラメータとして書き換える事を意味します。具体的な w(i, j) は

1.	j2 = ( j + 1 ) (mod) M
2.	K[i].a = ( K[j].a * K[i].a + K[j].b ) (mod) FEC5
3.	K[i].b = ( K[j2].a * K[i].b + K[j2].b ) (and) 7FFF

の通りです。

上記により算出された擬似乱数列 { Xk } より以下の式により、FSRansu の出力乱数列 { Rk }を生成します。

Rk = Xk (and) FF, (k = 1, 2, ... )

なお、今回使用したアファイン鍵数、各アファイン鍵の寿命及び鍵の使用回数の初期値は以下の通りです。

アファイン鍵の数	M	64
各アファイン鍵の寿命	K[i].n, (i=0, .., 63)K[i].n, (i=0, .., 63)	3
各アファイン鍵の使用回数の初期値	K[i].c, (i=0, .., 63)	K[i].a (mod) K[i].n

FSAngoによる暗号化／復号化方法
FSAngoの様なストリーム暗号は平文と擬似乱数の排他的論理和を取り暗号文を生成します。つまり平文列、暗号文列、擬似乱数列をそれぞれ {mk}, {ck}, {Rk} とすると

{ck} = {mk} (xor) {Rk}

となります。ここで{ck}にさらに{Rk}と排他的論理和を取るとその結果{m'k}は

{m'k} = {ck} (xor) {Rk} = {mk} (xor) {Rk} (xor) {Rk} = {mk} (xor) ({Rk} (xor) {Rk}) = {mk}

となり元の平文を得ることが出来ます。したがって問題文（暗号文）{ck} を復号するには FSRansuで求めた擬似乱数列と問題文の排他的論理和を取ることで復号化出来ます。

下表に先頭１０バイト (k = 1，.. , 10) の暗号文 ck と擬似乱数列 Xk, Rk 及び平文 mk を示します。また同時に使用されたアファイン鍵 i (=0〜63) 及び擬似乱数生成時の鍵書換えの有無を示します。

k		1	2	3	4	5	6	7	8	9	10
暗号文: ck		77	17	15	1d	a2	70	8c	82	59	e8
擬似乱数列: Xk		4c3e	7263	4e35	3374	60d1	0450	71fe	41e3	382d	6980
擬似乱数列: Rk		3e	63	35	74	d1	50	fe	e3	2d	80
平文: mk	１６進数	49	74	20	69	73	20	72	61	74	68
平文: mk	ASCII	I	t		i	s		r	a	t	h
選択されたアファイン鍵: i		0	12	50	14	51	32	4	49	1	56
鍵書換えの有無		有	有	無	無	有	無	無	有	無	無

【注意】本仕様は「FSAngo」解読コンテストで使用しているアルゴリズムとは異なります

コンテストの状況

１年間にわたり、FSAngo解読コンテストにご支援を頂きありがとうございました。また、問題文のダウンロード時のアンケートにご協力頂きありがとうございました。

コンテスト期間中は約１万６千件もの問題文のダウンロードを頂きました。そのうち海外からは３２１件のダウンロードを頂いています。解答は２件ありましたがいずれも不正解でした。

問題文のダウンロード状況を以下に示します。

日本	15,405件
外国	321件
合計	15,726件

カタログお問い合わせ

FSAngo解読

懸賞問題

コンテストの状況

個人のお客様

法人のお客様

会社情報

IR情報

サステナビリティ