RSA暗号で「ふっかつのじゅもん」を作る(3)-完結
Pythonを使って高速素数判定をしてみる - Pashango’s Blog
RSA暗号で「ふっかつのじゅもん」を作る(1) - Pashango’s Blog
RSA暗号で「ふっかつのじゅもん」を作る(2) -RSA暗号鍵の生成
当初はサクッと終わらせるつもりだったのに、意外と長くなってしまいました。
ドラクエ１の「ふっかつのじゅもん」の仕様
まず、ドラクエ１の「ふっかつのじゅもん」の仕様を調べてみました。
- 使われる文字は64種類のひらがなと数字
- じゅもんの長さは20文字まで
- 以下の情報を含む
- なまえ(0〜63までの数値×4）
- 魔法の鍵(0〜7までの数値）
- 薬草(0〜7までの数値）
- ぶき(0〜7までの数値）
- ぼうぐ(0〜7までの数値）
- たて(0〜3までの数値）
- アイテム(0〜15までの数値×8）
- フラグ(0〜1までの数値×5）
- 経験値(0〜65535までの数値）
- ゴールド(0〜65535までの数値）
呪文の長さは20文字ですので、情報量は6bit×20文字=120bitとなります。
そのうち、最上位bitはRSA暗号化時に失われる可能性がありますので、データ保持として使えるbit数は119bitとなります。
また、上記の情報を保存するのに必要なbit数は107bitですので、119-107=12bitの余裕bitがあります。
暗号鍵を求める(eとdを求める）
前回、暗号鍵の元となる素数p,qを求めましたね。
私もすっかり忘れていましたが、乗数であるeとdを求める関数を作りましょう。
前回のgenerate_pq()と一緒のファイルに書き足してください。
def generate_ed(p,q): """与えられた素数ペアからe,dを生成""" if p*q < 5: raise ValueError,"p*q must be large than 4." l = lcm(p-1,q-1) e = random.randint(5,l-1) | 1 while True: e = e+2 if e+2 <= l-1 else 5 if gcd(e,l) == 1: break d = gcd2(e,l)[0] if d < 0: d += l return (e,d)
さっそく、鍵を生成してみましょう。
ふっかつのじゅもんに必要なbit数は120bitですので、以下のように求めます。
p,q = generate_pq(120) e,d = generate_ed(p,q) n = p*q # p = 96568316136941074427 # q = 7372545182284901 # n = 711954273896770180320412909759326727 # e = 26578325672224134549282406558845001 # d = 34518827246730708105140436249657601
pとqはn,e,dが求まれば不要ですので、廃棄してください。
「公開鍵」がeとn、「秘密鍵」がdとnの数値ペアとなります。
勇者の情報を生成する
暗号化する勇者の情報を生成するクラスを作成しました。
このクラスはパラメータの乱数生成に加え、パラメータ＜-＞107bit数値の相互変換機能を持っています。
以下、コードですが特に面白味もないコードなので、サラッと読み飛ばしてください。
#coding:utf8 import random class DQParams(object): NAMES_CHARS = u"＊あいうえおかきくけこさしすせそたちつてと"\ u"なにぬねのはひふへほまみむめもやゆよ"\ u"らりるれろわをんっゃゅょ ー"\ u"０１２３４５６７８９S" PARAM_INFO = [ {'name':u"なまえ",'max':len(NAMES_CHARS),'len':4}, {'name':u"魔法の鍵",'max':8,'len':1}, {'name':u"薬草",'max':8,'len':1}, {'name':u"ぶき",'max':8,'len':1}, {'name':u"ぼうぐ",'max':8,'len':1}, {'name':u"たて",'max':4,'len':1}, {'name':u"アイテム",'max':16,'len':8}, {'name':u"フラグ1",'max':2,'len':5}, {'name':u"経験値",'max':65535+1,'len':1}, {'name':u"ゴールド",'max':65535+1,'len':1} ] def __init__(self, val=None): self.params = {} for x in self.PARAM_INFO: self.params[x['name']] = [0] * x['len'] if val == None: val = random.randint(0,1<<120) dec = lambda val,max:(val/max,val%max) for x in reversed(self.PARAM_INFO): for y in range(x['len']): val,self.params[x['name']][y] = dec(val, x['max']) self.params[x['name']].reverse() def name2val(self, name): return [self.NAMES_CHARS.index(x) for x in name] def val2name(self, val): return ''.join([self.NAMES_CHARS[x] for x in val]) def generate_value(self): val = 0 for x in self.PARAM_INFO: for y in self.params[x['name']]: val = val*x['max'] + y return val def output(self): f = self.PARAM_INFO[0] print f['name'],u"：",self.val2name(self.params[f['name']]) for x in self.PARAM_INFO[1:]: print x['name'],u"：",self.params[x['name']]
それでは、さっそく勇者を生成してみましょう。
obj = DQParams() obj.output() #なまえ ： かんてつ #魔法の鍵 ： [3L] #薬草 ： [0L] #ぶき ： [2L] #ぼうぐ ： [1L] #たて ： [3L] #アイテム ： [4L, 12L, 12L, 1L, 4L, 0L, 0L, 14L] #フラグ1 ： [1L, 1L, 0L, 1L, 1L] #経験値 ： [46633L] #ゴールド ： [6040L] val = obj.generate_value() #val => 17045993125123514293179659130776
おお、よくきたな、ゆうしゃかんてつよ、
今後は、生成された勇者「かんてつ」のパラメータを使います。
チェックサムとランダム値
今回の仕様では、必要情報量107bitー最大情報量119bitで差し引き12bitの余裕bitがあります。
この12bitに「チェックサム」と「ランダム値」を埋め込みます。
「チェックサム」は、この数値が正当あるかのチェックに使われ、適当に入力された呪文をはじく効果があります。
「ランダム値」は、データ値に乱数を埋め込むことにより、同じパラメータを暗号化しても毎回呪文が変わるようになり、暗号解析がしにくくなります。
今回の例では12bitの余裕bitのうち、チェックサムに9bit、ランダム値に3bitを割り当てます。
以下、出力された数値にチェックサムとランダム値を埋め込むコードです。
def check_sum(val,base=1<<9): csum = 0 while val > 0: csum += val%(base-1) csum %= base val /= base csum = (base-1)-csum return csum csum = check_sum(val) #csum => 114 val = (val << 9) + csum val = (val << 3) + random.randint(0,7) #val => 69820387840505914544863883799659408
なお、チェックサムは((1<<9)-1)から引いた値になっていますが、これはvalが0にならないようにするためです。
valが0ですと暗号化した結果も0になってしまい、暗号になっていません。
チェックサムのビットを反転する事により、valに0が入る事を防いでいます。
「ふっかつのじゅもん」を生成
ここまで長い道のりでしたが、ようやく「ふっかつのじゅもん」を生成します。
val = 69820387840505914544863883799659408 n = 711954273896770180320412909759326727 e = 26578325672224134549282406558845001 d = 34518827246730708105140436249657601 val = pow(val,e,n) #val => 692554535384224777977608304993455189 PASS_CHARS = u"あいうえおかきくけこさしすせそたちつてと"\ u"なにぬねのはひふへほまみむめもやゆよわ"\ u"らりるれろ"\ u"がぎぐげござじずぜぞだぢづでどばびぶべぼ" s = [] while True: s.append(PASS_CHARS[val%64]) val /= 64 if val <= 0: break print "".join(s) # にざぜくねだひかづそぎけあぬへさときぬめ
勇者「かんてつ」のふっかつのじゅもんは「にざぜくねだひかづそぎけあぬへさときぬめ」となりました。
さっそく、復活できるかチェックしてみましょう。
n = 711954273896770180320412909759326727 d = 34518827246730708105140436249657601 val = 692554535384224777977608304993455189 val = pow(val,d,n) csum = (val>>3) & ((1<<9)-1) val >>= 12 csum2 = check_sum(val,1<<9) if csum != csum2: print u"ふっかつのじゅもんがちがいます" else: obj = DQParams(val) obj.output() #なまえ ： かんてつ #魔法の鍵 ： [3L] #薬草 ： [0L] #ぶき ： [2L] #ぼうぐ ： [1L] #たて ： [3L] #アイテム ： [4L, 12L, 12L, 1L, 4L, 0L, 0L, 14L] #フラグ1 ： [1L, 1L, 0L, 1L, 1L] #経験値 ： [46633L] #ゴールド ： [6040L]
ゆうしゃかんてつよ、よくぞもどってきた
RSA暗号化 vs 旧来の暗号化
RSA暗号化による暗号化と、旧来の暗号化の違いはなんでしょうか？
まずは、保存可能な情報量の違いから。
旧来の暗号化はまるまる120bitに情報を詰め込めます、RSA暗号化は最上位ビットが不定になりますので119bitしか使えません。
余った情報はチェックサムに使われますので、RSA暗号化の方がチェックサムが1bit少なくなります、これはどういう事かと言いますと、適当に打ち込んだ呪文が通ってしまう確率が旧来暗号化に比べて2倍高いという事です。
一方、RSA暗号のメリットは、やはり暗号化と複合化に使われる鍵が２つにわかれている点でしょう。
旧来暗号化の弱点は、暗号化と複合化が必ずセット提供されてしまう点です。
「暗号化の手順＝復号化の逆手順」であり、そのまた逆も然りです。
リバースエンジニアリングにより、暗号化の手順が解析されてしまうと、自動的に復号化の手順も解析されてしまうのです。
一方、RSA暗号では、暗号化と復号化のどちらか一方のみの提供が出来ます。
暗号化はサーバーで行い、クライアントは復号化しかできないという扱いも可能です。
（RSA暗号でも、クライアントに暗号鍵と復号鍵を埋め込んだらリバースエンジニアリングには無力ですよ、念のため）
うんうん、なんか使えそうなんだけど、意外と使いどころが難しい技術ですね。
でも、工夫次第ですごい面白い事もできそうです。
