LoginSignup
0
1

More than 3 years have passed since last update.

正数の暗号化

Last updated at Posted at 2020-10-05

正数の暗号化

0から始まる正の数を暗号化します。1,2,3と素直にインクリメントされた数字をユーザーID等に使用した場合に総当りハッキングがやりやすい状況となります、安易なインクリメントによる総当り攻撃を防ぐためにランダム文字列かつインクリメントにも対応したID生成を行いたいというのが本件の動機です。
実行例を示します。


0 -> 052C5C223627156D7
1 -> 1572257C261D2C376
2 -> 252C1C627627952D3
3 -> 352CEC223627156D7
4 -> 452C1C627627452D3
5 -> 552C1C627627F52D3
6 -> 6512253C662D2C772
7 -> 75D2257C261D2C376
8 -> 8512253C663D2C772
9 -> 953D25C726726C1C2
10 -> A53D258726726C1C2

以上のように0~10とインクリメントしただけの数字がそれっぽく暗号化IDに変換されています。
以下、16進数文字列で16桁のIDを作成する事を前提として記します。

素数を使って桁の入れ替えを行う

暗号化したい数字を16進文字列へ変換し、その文字列のインデックスを素数で割った余りを対応桁として桁の交換を行います。

n = 9999
PrimeTable = [61, 31, 53, 29, 37, 5, 23, 47, 7, 59, 43, 3, 17, 13, 19, 41, 11]
mod = n % 16 # mod = 15
mod = int(enc[0], 16)
prime = PrimeTable[mod] # prime = 41
for i in range(16):
    dig = (i * prime) % 16
# 対応桁 => 0, 9, 2, 11, 4 ,13, 6, 15, 8, 1, 10, 3, 12, 5, 14, 7

通常は右から低い位が始まり左が大きな位ですが、対応桁をシャッフルすることで安易なインクリメントを回避します。

注意点

注意点として桁数と同じ素数は選択しない事があります、17桁のIDにしたい場合に17を使って桁数のシャッフルを行おうとすると全て0桁目となってしまいます。

>dig = (i * prime) % 16
↓
>dig = (i * 17) % 17
iの値をどんなものにしてもdigは0にしかならない

乱数テーブルによる16進数文字列の置き換え

桁をシャッフルしても各桁の数字が0から始まりFで終わるようだとある程度IDの推定が行えます、そこで0~Fを対応テーブルの結果で置き換えます。
以下のようなテーブルを作成し各桁の数字に対応させます。
テーブルを動的に生成する等の自動化できそうにも思いましたがこれ以上の処理も思いつかなかったのでテーブルを埋め込む形で実装しています。


digitsTable = [
    [5, 3, 15, 14, 11, 7, 6, 2, 12, 8, 10, 13, 4, 1, 9, 0],
    [6, 5, 13, 7, 15, 11, 14, 12, 0, 8, 2, 9, 3, 4, 1, 10],
    [7, 0, 11, 15, 2, 13, 12, 6, 4, 10, 9, 5, 1, 3, 14, 8],
    [3, 6, 13, 7, 5, 10, 14, 0, 1, 9, 15, 4, 11, 8, 2, 12],
    [12, 10, 2, 3, 4, 5, 6, 15, 7, 11, 13, 0, 14, 9, 1, 8],
    [2, 10, 13, 14, 0, 1, 12, 6, 3, 15, 11, 5, 9, 7, 8, 4],
    [13, 8, 9, 14, 0, 15, 1, 3, 2, 11, 5, 12, 7, 4, 10, 6],
    [1, 10, 15, 7, 14, 6, 12, 11, 2, 8, 4, 5, 13, 0, 9, 3],
    [6, 4, 7, 1, 12, 8, 10, 0, 15, 14, 9, 13, 5, 11, 3, 2],
    [2, 14, 13, 15, 6, 11, 10, 7, 3, 8, 1, 4, 5, 0, 9, 12],
    [12, 4, 2, 5, 10, 3, 0, 11, 8, 14, 13, 1, 7, 6, 15, 9],
    [7, 1, 14, 5, 0, 2, 9, 12, 8, 6, 4, 3, 11, 10, 15, 13],
    [5, 8, 4, 2, 11, 10, 7, 14, 3, 0, 12, 6, 9, 13, 1, 15],
    [2, 4, 14, 13, 15, 10, 7, 6, 9, 11, 1, 0, 12, 3, 8, 5],
    [2, 14, 9, 11, 5, 3, 6, 1, 12, 13, 8, 4, 15, 7, 0, 10],
    [5, 7, 9, 14, 4, 15, 2, 13, 3, 12, 8, 1, 10, 6, 11, 0],
]

実験ソースコード


digitsTable = [
    [5, 3, 15, 14, 11, 7, 6, 2, 12, 8, 10, 13, 4, 1, 9, 0],
    [6, 5, 13, 7, 15, 11, 14, 12, 0, 8, 2, 9, 3, 4, 1, 10],
    [7, 0, 11, 15, 2, 13, 12, 6, 4, 10, 9, 5, 1, 3, 14, 8],
    [3, 6, 13, 7, 5, 10, 14, 0, 1, 9, 15, 4, 11, 8, 2, 12],
    [12, 10, 2, 3, 4, 5, 6, 15, 7, 11, 13, 0, 14, 9, 1, 8],
    [2, 10, 13, 14, 0, 1, 12, 6, 3, 15, 11, 5, 9, 7, 8, 4],
    [13, 8, 9, 14, 0, 15, 1, 3, 2, 11, 5, 12, 7, 4, 10, 6],
    [1, 10, 15, 7, 14, 6, 12, 11, 2, 8, 4, 5, 13, 0, 9, 3],
    [6, 4, 7, 1, 12, 8, 10, 0, 15, 14, 9, 13, 5, 11, 3, 2],
    [2, 14, 13, 15, 6, 11, 10, 7, 3, 8, 1, 4, 5, 0, 9, 12],
    [12, 4, 2, 5, 10, 3, 0, 11, 8, 14, 13, 1, 7, 6, 15, 9],
    [7, 1, 14, 5, 0, 2, 9, 12, 8, 6, 4, 3, 11, 10, 15, 13],
    [5, 8, 4, 2, 11, 10, 7, 14, 3, 0, 12, 6, 9, 13, 1, 15],
    [2, 4, 14, 13, 15, 10, 7, 6, 9, 11, 1, 0, 12, 3, 8, 5],
    [2, 14, 9, 11, 5, 3, 6, 1, 12, 13, 8, 4, 15, 7, 0, 10],
    [5, 7, 9, 14, 4, 15, 2, 13, 3, 12, 8, 1, 10, 6, 11, 0],
]

# 復号化のために逆引きテーブルを作成しておく
digitsReverseTable = []
for tbl in digitsTable:
    a = [0] * 16
    for i, v in enumerate(tbl):
        a[v] = i
    digitsReverseTable.append(a)

PrimeTable = [61, 31, 53, 29, 37, 5, 23, 47, 7, 59, 43, 3, 17, 13, 19, 41, 11]
def encodeNumber(n):
    hexStr = "00000000000000000000" + "{:X}".format(n)
    hexStr = hexStr[-16:]
    mod = n % 16
    prime = PrimeTable[mod]
    enc = [""] * 16
    for i in range(16):
        c = hexStr[i]
        dig = (i * prime) % 16
        idx = int(c, 16)
        m = digitsTable[i][idx]
        enc[dig] = "{:X}".format(m)
    # 復号化のために mod をIDに残しておく
    return "{:X}".format(mod) + "".join(enc)

def decodeNumber(enc):
    mod = int(enc[0], 16)
    prime = PrimeTable[mod]
    enc = enc[1:]
    numArr = [0] * 16
    for i in range(16):
        dig = (i * prime) % 16
        ridx = int(enc[dig], 16)
        m = digitsReverseTable[i][ridx]
        numArr[i] = m
    numArr = list(reversed(numArr))
    n = 0
    for i in range(16):
        n += numArr[i] * 16 ** i
    return n

def main():
    for i in range(0, 100):
        enc = encodeNumber(i)
        print(i, enc, decodeNumber(enc))

if __name__ == "__main__":
    main()
# python encode_counter.py

実行結果

0 052C5C223627156D7 0
1 1572257C261D2C376 1
2 252C1C627627952D3 2
3 352CEC223627156D7 3
4 452C1C627627452D3 4
5 552C1C627627F52D3 5
6 6512253C662D2C772 6
7 75D2257C261D2C376 7
8 8512253C663D2C772 8
9 953D25C726726C1C2 9
10 A53D258726726C1C2 10
11 B57D651726322C1C2 11
12 C5673C2D162C7522A 12
13 D52C6C223627156D7 13

途中省略

89 953D25C726736C1C2 89
90 A53D258726736C1C2 90
91 B57D651726332C1C2 91
92 C5673C2D162C7523A 92
93 D52C6C233627156D7 93
94 E57D651726332CBC2 94
95 F5277C2D066C35231 95
96 052C5C263627156D7 96
97 1576257C261D2C376 97
98 252C1C667627952D3 98
99 352CEC263627156D7 99

実際の使用について

そのまま使うよりかは2~4文字置きにランダムにダミー文字列を挟む等したほうが尚良いと思います、当然とは思いますが記載のサンプルソースをそのまま使うような事も避けます。

もっと楽で分かりやすいやり方

予めIDを発行する事で本件のような込み入ったロジックを使わずに済みます。
作ろうとしているシステムにおいて「1万件あれば足りる」等と上限が想定できる場合はランダム文字列で予めIDを1万件発行しておいて0~9999に紐づけたテーブルを作成し使う時にはその対応テーブルを使用します。
注意点としてはIDがユニークであることを保障するための検査を忘れずに実行します。

既にありそう

こういう処理は需要高そうなので既存ライブラリにありそうだなと思いながら作っていました、ただこの概念をなんと言うのか分からず検索ワードも思いつかないので自作しました、同じようなことをするライブラリあればコメントで教えて下さい。
以上です。

0
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1