suyumen
目前主要在学习web相关

部分古典密码实现

2022-03-20 js 密码
Word count: 2.3k | Reading time: 12min

  • 加密：仿射密码加密结果为：[14,25,18]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const p = [7, 14, 19];
    const k = [9, 3];
    let value = [];

    function encode(p, k, value) {//加密
        let l = p.length;
        for (let i = 0; i < l; i++) {
            value.push((p[i] * k[0] + k[1]) % 26);
        }
    }

    encode(p, k, value);
    console.log("仿射密码加密结果为：[" + value.toString() + "]");

  • 解密：
    仿射密码解密结果为：[7,14,19]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    const k = [9, 3];
    const c = [14, 25, 18];
    let value = [];
    let v = [];

    function decode(c, k, value) {//解密
        let l = c.length;
        exgcd(26, k[0], v);
        for (let i = 0; i < l; i++) {
            let m = (c[i] - k[1]) * v[1] % 26;
            if (m < 0) m += 26;
            value.push(m);
        }
    }

    function exgcd(a, b, v) {//扩展欧几里得算法求逆
        if (b === 0) {
            v.push(1);
            v.push(0);
        } else {
            exgcd(b, a % b, v);
            let tmp = v[0];
            v[0] = v[1];
            v[1] = tmp - Math.floor(a / b) * v[1];
        }
    }

    decode(c, k, value);
    console.log("仿射密码解密结果为：[" + value.toString() + "]");

    2

    维吉尼亚加密结果为：rzqpmx ovgd fwcl qvugmvy br jgqdtn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const p = "please keep this message in secret";
const k = "computer";

function encode(p, k) {
    let l = k.length;
    let c = "";
    for (let i = 0, j = 0; i < p.length; i++) {
        if (p[i] >= 'a' && p[i] <= 'z') {
            c += String.fromCharCode(((p[i].charCodeAt(0) + k[j % l].charCodeAt(0) - 2 * 'a'.charCodeAt(0)) % 26 + 'a'.charCodeAt(0)));
            j++;
        } else {
            c += p[i];
        }
    }
    return c;
}

console.log("维吉尼亚加密结果为："+encode(p, k));

3

Hill密码加密结果为：[j,i,i,y]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const k = [[8, 6, 9, 5], [6, 9, 5, 10], [5, 8, 4, 9], [10, 6, 11, 4]];
const i = 4;//矩阵宽度
const p = "hill";

function decode(p, k, i) {
    let l = p.length;
    let n = [[]];
    let j, r;
    for (j = 0, r = 0; j < l / 4 && r < l; r++) //明文字符串转矩阵
        n[j].push(p.charCodeAt(r) - 'a'.charCodeAt(0));
    j = Math.floor(r / 4);
    console.log("Hill密码加密结果为：[" + matrMul(n, k, i, j).toString() + "]");
}

function matrMul(n, k, i, j) {//矩阵乘法
    let value = [];
    for (let r = 0; r < j; r++) {
        value[r] = [];
        for (let h = 0; h < i; h++) {
            value[r][h] = 0;
            for (let q = 0; q < i; q++) {
                value[r][h] += n[r][q] * k[q][h];
            }
            value[r][h] = String.fromCharCode((value[r][h] % 26 + 'a'.charCodeAt(0)));
        }
    }
    return value;
}

decode(p, k, i);

4

仿射密码密钥生成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function generate_k() {//密钥生成
    let k = [];
    k[0] = Math.floor(Math.random() * 25 + 1);//选取1-25随机数
    k[1] = Math.floor(Math.random() * 25 + 1);
    while (husu(26,k[1] )!==true) {
        k[1] = Math.floor(Math.random() * 25 + 1);
    }
    return k;
}

function husu(a, b) {//互素判断--若gcd(a,b)=1，则互素
    let r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a === 1;
}

仿射密码加密：

1
2
3
4
5
6
7
8
9
10
11
12
function encode(p, k) {//加密
    let l = p.length;
    let value = "";
    for (let i = 0; i < l; i++) {
        if (p[i] >= 'a' && p[i] <= 'z') {
            value += String.fromCharCode((((p.charCodeAt(i) - 'a'.charCodeAt(0)) * k[0] + k[1]) % 26) + 'a'.charCodeAt(0));
        } else {
            value += p[i];
        }
    }
    return value;
}

仿射密码惟密文解密：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
function decode(c) {//惟密文解密
    let value = "";
    let l = c.length;
    let fre = new Array(26)
    for (let i = 0; i < 26; i++) {
        fre[i] = new Array(2);
        fre[i][0] = i;
        fre[i][1] = 0;
    }
    for (let i = 0; i < l; i++) {
        if (c[i] >= 'a' && c[i] <= 'z') {
            fre[c.charCodeAt(i) - 'a'.charCodeAt(0)][1]++;//统计各字母出现次数
        }
    }
    bubbleSort(fre);//按字母出现频率排序
    let v = [];
    for (let j = 1; j < 26; j++) {
        let x = DivideTwoCellOnce(fre[0][0], fre[j][0]);
        if (!husu(x[0], 26)) {//不互素--选取不合适
            continue;
        }
        exgcd(26, x[0], v);//求a逆
        for (let i = 0; i < l; i++) {
            if (c[i] >= 'a' && c[i] <= 'z') {
                let m = (c.charCodeAt(i) - 'a'.charCodeAt(0) - x[1]) * v[1] % 26
                if (m < 0)
                    m += 26;//保证取正数
                value += String.fromCharCode('a'.charCodeAt(0) + m);
            } else {
                value += c[i];
            }
        }
        console.log(value.toString());
        value = "";
    }
}

function DivideTwoCellOnce(x, y) {//模除
    while ((y - x) % 15 !== 0) {
        y += 26;
    }//保证a为整数
    let a = (y - x) / 15;
    while (x - a * 4 < 0) {
        x += 26;
    }
    let b = x - a * 4;
    return [a, b];
}

function exgcd(a, b, v) {//扩展欧几里得算法求逆
    if (b === 0) {
        v.push(1);
        v.push(0);
    } else {
        exgcd(b, a % b, v);
        let tmp = v[0];
        v[0] = v[1];
        v[1] = tmp - Math.floor(a / b) * v[1];
    }
}

function bubbleSort(fre) {
    let l = fre.length;
    for (let i = 0; i < l; i++) {
        for (let j = 0; j < l - 1 - i; j++) {
            if (fre[j][1] < fre[j + 1][1]) {        //相邻元素两两对比
                let tmp = fre[j + 1];        //元素交换
                fre[j + 1] = fre[j];
                fre[j] = tmp;
            }
        }
    }
}

单表代换密钥生成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function generate_k(){
    let k = [...new Array(25).keys()];
    arr_random(k);
    return k;
}
function arr_random(arr){//数组随机排序
    let index=arr.length;
    while(index)
    {
        let random=Math.floor(Math.random()*index);
        index--;
        let tmp=arr[index];
        arr[index]=arr[random];
        arr[random]=tmp;
    }
}

单表代换加密：

1
2
3
4
5
6
7
8
9
10
11
12
function encode(p, k) {
    let c = "";
    let l = p.length;
    for (let i = 0; i < l; i++) {
        if (p[i] >= 'a' && p[i] <= 'z') {
            c += String.fromCharCode('a'.charCodeAt(0) + k[p.charCodeAt(i) - 'a'.charCodeAt(0)]);
        } else {
            c += p[i];
        }
    }
    return c;
}

单表代换解密：

1
2
3
4
5
6
7
8
9
10
11
12
function decode(c, k) {
    let p = "";
    let l = c.length;
    for (let i = 0; i < l; i++) {
        if (c[i] >= 'a' && c[i] <= 'z') {
            p += String.fromCharCode('a'.charCodeAt(0) + k.findIndex(value => value === c.charCodeAt(i) - 'a'.charCodeAt(0)));
        } else {
            p += c[i];
        }
    }
    return p;
}

5

穷尽搜索的复杂度:
| | |
| – | – |
|移位|$25$|
|仿射| $\Phi (26)*26=312$|
|单表代换|$26!$|
|维吉尼亚|$26^m$|
|多表代换|$26^m$|
|置换:|$m!$|

6

分组加密:多表代换，置换密码，希尔密码。
因为他们都要先将明文分组，然后分别和密钥进行加密操作。

7

猜测密钥长度为：7
密钥对应数字为：15,17,14,20,3,4,17
解密结果为andfinallybuildacommunitynoonedoesbigthingsbythemselvesrightnowwhenpeoplearescareditiseasytobecynicalandsayletmejustlookoutformyselformyfamilyorpeoplewholookor
thinkorpraylikemebutifwearegoingtogetthroughthesedifficulttimesifwearegoingtocreateaworldwhereeverybodyhastheopportunitytofindajobandaffordcollegeifwearegoingtosavetheen
vironmentanddefeatfuturepandemicsthenwearegoingtohavetodoittogether

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
let c = "Per zlrracm, vxmcs r qipqlczhs. Qs fcv rihw sxxhblrxh sm nkidhvzphw. Ixxvn qsn, lysh sifecs uuijrrfyg, mk xj suvc kd ss wbrzrrz uqh jpp zyw qv ylgn osfz fin isi bpgyoj, fg dm zdqzap, cl sifecsqks cdfy iu xyxey iu tipp zcni dt. Sin lj nt rfy jszcxhi jik iyfixky iysmh hzuwwwxpk izayv; mw lv olhkfxeu nr gitrhy d afgcr qkiit vjyucsdum bdw kwvcjssiilbcwc kd wwhg e ads, ohg ewuffx fscavuy; ljnt rfy jszcx hi vemt kvy hrmxichpiei rbx giwtrhzxxlgv duqhvbzqm, wlvc ns uui xdzba ws ypmsnr hf xk hijikwvf."
c = pre(c);
let key = exp(c);
console.log("解密结果为" + decode(key, c.length, c).toString());

function pre(c) {//去掉非字母符号，方便计算index
    return c.toLowerCase().match(/[a-z]/g).join("");
}

function Kasiski(c, l) {//猜解秘钥长度
    let n = 0;
    let value = [];//间距数组
    for (let i = 0; i + 5 < l; i++) {//一个一个试？不知道有没有更好的方法
        let substr = c.substring(i, i + 3);
        let begin = i;
        let j = KMP(c.substring(begin + 3), substr);//当前位置+3向后到匹配j
        while (j !== -1)//匹配到了
        {
            if (value.indexOf(j + 3) === -1) {
                value[n] = j + 3;
                n += 1;
            }
            begin += j + 3;
            j = KMP(c.substring(begin + 3), substr);
        }
        if (value[4]) break;//取5个间隔
    }
    for (let i = 0; i < n - 1; i++) {
        value[i + 1] = gcd(value[i], value[i + 1]);
    }
    return value[n - 1];
}

function exp(c) {//拟重合指数法确认密钥
    let q = [8.19, 1.47, 3.83, 3.91, 12.25, 2.26, 1.71, 4.57, 7.10, 0.14, 0.41, 3.77, 3.34, 7.06, 7.26, 2.89, 0.09, 6.85,
        6.36, 9.41, 2.58, 1.09, 1.59, 0.21, 1.58, 0.08]
    let l = c.length;
    let key = [];
    let key_length = Kasiski(c, l);
    console.log("猜测密钥长度为：" + key_length);
    for (let j = 0; j < key_length; j++) {
        let val = divide_c(c, l, key_length, j);
        let p = new Array(26).fill(0);
        for (let j = 0; j < l; j++)
            p[val.charCodeAt(j) - 'a'.charCodeAt(0)]++;//统计各字母出现次数
        to_fre(p, 26);//处理为频率
        key[j] = correlation(p, q);//算卷积
    }
    console.log("密钥对应数字为：" + key.toString());
    return key;
}

function decode(key, l, c) {
    let key_length = key.length;
    let v = "";
    for (let i = 0; i < l; i++)
        v += String.fromCharCode((c.charCodeAt(i) - 'a'.charCodeAt(0) - key[i % key_length] + 26) % 26 + 'a'.charCodeAt(0));
    return v;
}


function divide_c(c, l, key, time) {//密文分组的第time列
    let div = "";
    for (let i = time; i < l; i += key) {
        div += c[i];
    }
    return div;
}

function correlation(p, q) {//算卷积
    let max = 0, cor = 0, key;
    for (let i = 0; i < 26; i++) {
        cor = 0;
        for (let j = 0; j < 26; j++) {
            cor += p[(j + i) % 26] * q[j];
        }
        if (cor > max) {
            max = cor;
            key = i;
        }
    }
    return key
}


function to_fre(a, l) {//出现次数---->频率
    for (let i = 0; i < l; i++) {
        a[i] = (a[i] / l).toFixed(3);
    }
    return a;
}

function gcd(a, b) {//求最大公因数
    let r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

function kmpGetStrPartMatchValue(str) {//KMP算法字符串匹配
    let prefix = [];
    let suffix = [];
    let partMatch = [];
    for (let i = 0, j = str.length; i < j; i++) {
        let newStr = str.substring(0, i + 1);
        if (newStr.length === 1)
            partMatch[i] = 0;
        else {
            for (let k = 0; k < i; k++) {
                prefix[k] = newStr.slice(0, k + 1);
                suffix[k] = newStr.slice(-k - 1);
                if (prefix[k] === suffix[k])
                    partMatch[i] = prefix[k].length;
            }
            if (!partMatch[i])
                partMatch[i] = 0;
        }
    }
    return partMatch;
}

function KMP(sourceStr, searchStr) {//KMP字符串匹配
    let part = kmpGetStrPartMatchValue(searchStr);
//    let sourceLength = sourceStr.length;
    let searchLength = searchStr.length;
    let result;
    let i = 0;
//    let j = 0;
    for (; i < sourceStr.length; i++) {
        for (let j = 0; j < searchLength; j++) {
            if (searchStr.charAt(j) === sourceStr.charAt(i)) {
                if (j === searchLength - 1) {
                    result = i - j;
                    break;
                } else
                    i++;
            } else {
                if (j > 1 && part[j - 1] > 0)
                    i += (i - j - part[j - 1]);
                else
                    i = (i - j)
                break;
            }
        }
        if (result || result === 0)
            break;
    }
    if (result || result === 0)
        return result
    else
        return -1;
}

Author: suyumen

Link: https://suyumen.github.io/2022/03/20/2022-03-20-%E9%83%A8%E5%88%86%E5%8F%A4%E5%85%B8%E5%AF%86%E7%A0%81%E5%AE%9E%E7%8E%B0/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
CVE-2021-21315复现NextPost >
湖湘杯2021final-vote
CATALOG
  1. 1. 2
  2. 2. 3
  3. 3. 4
  4. 4. 5
  5. 5. 6
  6. 6. 7