密码学习题

---

班级: 09061401
学号: 2014302358
姓名: 林维

---

传统密码

加法密码

[1]

若加法密码中密钥K＝7，试求明文good night的密文。

const int alplen(26);
// ptx表示明文(plaintext), key表示密钥， ctx表示密文(ciphertext)
void additive_cipher(char *ptx, int key, char *ctx)
{
    int i;
    for(i = 0; ptx[i]; i++) {
        if(ptx[i] > 'z' || ptx[i] < 'a') {
            ctx[i] = ptx[i];
        }
        else {
            int c = ((ptx[i] - 'a') + key) % alplen;
            ctx[i] = 'a' + c;
        }
    }
    ctx[i] = '\0';
}

解得密文为 : nvvk upnoa

乘法密码

[2]

若乘法密码中密钥K＝5，试对明文network的加密。

const int alplen(26);
// ptx表示明文(plaintext), key表示密钥， ctx表示密文(ciphertext)
void multiplication_cipher(char *ptx, int key, char *ctx)
{
    int i;
    for(i = 0; ptx[i]; i++) {
        if(ptx[i] < 'a' || ctx[i] > 'z') {
            ctx[i] = ptx[i];
        }
        else {
            int c = ptx[i] - 'a';
            c = c * key % alplen;
            ctx[i] = 'a' + c;
        }
    }
    ctx[i] = '\0';
}

得到密文为 ： nurgshy

仿射变换

[3]

已知仿射变换为c＝5m+7(mod26)，试对明文help me加密

const int alplen(26);
// ptx表示明文(plaintext), key1、key2表示密钥， ctx表示密文(ciphertext)
void affine_transformation(char *ptx, int key1, int key2, char *ctx)
{
    int i;
    for(i = 0; ptx[i]; i++) {
        if(ptx[i] < 'a' || ptx[i] > 'z') {
            ctx[i] = ptx[i];
        }
        else {
            int c = ptx[i] - 'a';
            c = (c * key1 + key2) % alplen;
            ctx[i] = 'a' + c;
        }
    }
    ctx[i] = '\0';
}

得到加密的密文为 : qbke pb

[4]

已知仿射变换为c＝5m+7(mod26)，试对密文VMWZ解密

const int alplen(26);
// ptx表示ctx表示密文(ciphertext), key1、key2表示密钥, 明文(plaintext)
void re_affine_trans(char *ctx, int key1, int key2, char *ptx)
{
    int i, re_key1;
    // 求key1在模alplen情况下的逆
    for(re_key1 = 0; re_key1 < alplen; re_key1++) {
        if(re_key1 * key1 % alplen == 1) {
            break;
        }
    }
    for(int i = 0; ctx[i]; i++) {
        if(ctx[i] < 'A' || ctx[i] > 'Z') {
            ptx[i] = ctx[i];
        }
        else {
            int c = ctx[i] - 'A';
            c = (c - key2) * re_key1;
            c = (c % alplen + alplen) % alplen;
            ptx[i] = 'A' + c;
        }
    }
    ptx[i] = '\0';
}

得到解密的明文为 ： IBDO

[5]

已知下列密文是通过单表代替密码加密的结果，试求其明文。

YIF QFMZRW QFYV ECFMD ZPCVMRZW NMD ZVEJB TXCDD UMJN DIFEFMDZ CD MQ ZKCEYFCJMYR NCW JCSZR EXCHZ UNMXZ NZ UCDRJ XYYSMRT M EYIFZW DYVZ VYFZ UMRZ CRW NZ DZJJXZW GCHS MR NMD HNCMF QCHZ JMXJZW IE JYUCFWD JNZ DIR.

这个过程是手算的，结果如下 :

our friend from paris examined his empty glass with surprise as if evaporation had taken place while he wasnt looging i poured some more wine and he settled back in his chair face tilted up towards the sun.

Vignere密码

[6]

已知Vigenere密码的密钥为matrix，试对明文some simple cryptosystem加密

const int alplen(26);
//ptx表示明文(plaintext), key表示密钥, ctx表示密文(ciphertext)
void vignere(char *ptx, char *key, char *ctx)
{
    int i, j;
    for(i = 0, j = 0; ptx[i]; i++) {
        if(ptx[i] < 'a' || ptx[i] > 'z') {
            ctx[i] = ptx[i];
        }
        else {
            int c = ptx[i] - 'a' + (key[j++] - 'a');
            ctx[i] = 'a' + (c % 26);
            if(!key[j]) j = 0;
        }
    }
    ctx[i] = '\0';
}

得到加密的密文为 ： eofv afypev kokpmfavetxd

代数密码

[7]

若代数密码中密钥为best，试对明文good加密

const int alplen(26);
// ptx表示明文(plaintext), key1、key2表示密钥， ctx表示密文(ciphertext)
void algebraic_cipher(char *ptx, char *key, char *ctx)
{
    int i, j;
    for(i = 0, j = 0; ptx[i]; i++) {
        if(ptx[i] > 'z' || ptx[i] < 'a') {
            ctx[i] = ptx[i];
        }
        else {
            int c = ptx[i] - 'a', k = key[j++] - 'a';
            ctx[i] = 'a' + (c ^ k) % alplen;
            if(!key[j]) j = 0;
        }
    }
    ctx[i] = '\0';
}

得到加密的密文为 : hkcq

Hill 密码

[8]

假设Hill密码加密使用密钥$\begin{bmatrix} 4 & 9 \\ 3 & 7 \end{bmatrix}$，试对明文best加密

const int alplen(26), maxn(100);
// ptx表示明文(plaintext), key[maxn][maxn]表示密钥, 密钥的秩为k， ctx表示密文(ciphertext)
// 这里假设矩阵的大小不超过100
void hill_cipher(char *ptx, int key[][maxn], int l, char *ctx)
{
    int i = 0, c[maxn];
    while(ptx[i]) {
        for(int j = 0; j < l; j++) {
            c[j] = ptx[i + j] - 'a';
        }
        for(int j = 0, t; j < l; j++) {
            t = 0;
            for(int k = 0; k < l; k++) {
                t += key[j][k] *  c[k];
            }
            ctx[j + i] = 'a' + t % 26;
        }
        i += l;
    }
    ctx[i] = '\0';
}

得到加密的密文 : ofjf

[9]

假设Hill密码加密使用密钥$\begin{bmatrix} 4 & 9 \\ 3 & 7 \end{bmatrix}$，试对密文UMFL解密。

const int alplen(26), maxn(100);
// ptx表示明文(plaintext), key[2][2]表示密钥， ctx表示密文(ciphertext)
void re_hill_cipher(char *ctx, int key[2][2], char *ptx)
{
    int re_key[2][2] = {key[1][1], -key[0][1], -key[1][0], key[0][0]};
    int detKey = key[0][0] * key[1][1] - key[0][1] * key[1][0], re_detKey;
    for(int i = 0; i < 26; i++) {
        if(detKey * i % alplen == 1) {
            re_detKey = i;
            break;
        }
    }
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            re_key[i][j] = re_key[i][j] * re_detKey % alplen;
            re_key[i][j] = (re_key[i][j] + alplen) % alplen;
        }
    }
    int i = 0, c[2];
    while(ctx[i]) {
        for(int j = 0; j < 2; j++) {
            c[j] = ctx[j + i] - 'a';
        }
        for(int j = 0; j < 2; j++) {
            int ans = 0;
            for(int k = 0; k < 2; k++) {
                ans += re_key[j][k] * c[k];
            }
            ptx[i + j] = 'a' + ans % alplen;
        }
        i += 2;
    }
    ptx[i] = '\0';
}

得到相应的明文 ： GOOD

[10]

假设明文friday利用的Hill密码加密，得到密文PQCFKU，试求密钥K

void key_hill_cipher(char *ptx, char *ctx, int key[2][2])
{
    int p[6], c[6], t = strlen(ptx);
    for(int i = 0; i < t; i++) {
        p[i] = ptx[i] - 'a', c[i] = ctx[i] - 'a';
    }
    for(int i = 0; i < alplen; i ++) {
        for(int j = 0; j < alplen; j++) {
            int sig;
            for(sig = 0; sig < t; sig += 2) {
                if((p[sig] * i + p[sig + 1] * j) % alplen != c[sig]) {
                    break;
                }
            }
            if(sig < t) continue;
            key[0][0] = i, key[0][1] = j;
            for(int k = 0; k < alplen; k++) {
                for(int l = 0; l < alplen; l++) {
                    for(sig = 0; sig < t; sig += 2) {
                        if((p[sig] * k + p[sig + 1] * l) % alplen != c[sig + 1])
                            break;
                    }
                    if(sig >= t) {
                        key[1][0] = k, key[1][1] = l;
                        return ;
                    }
                }
            }
        }
    }
}

解得密钥 $K = \begin{bmatrix} 7 & 8 \\ 19 & 3 \end{bmatrix}$

分组密码

DES

[1]

设DES数据加密标准中：
明文

m = 0011 1000 1101 0101 1011 1000 0100 0010 1101 0101 0011 1001 1001 0101 1110 0111

密钥

K = 1010 1011 0011 0100 1000 0110 1001 0100 1101 1001 0111 0011 1010 0010 1101 0011

试求L1与R1。

#include <bits/stdc++.h>
using namespace std;
const int maxn(70);
void output(bool *t, int l)
{
    for(int i = 1, d = 1; i <= l / 4; i++) {
        for(int j = 0; j < 4; j++) {
            cout<<t[d++];
        }
        cout<<' ';
    }
    cout<<endl;
    cout<<"--------------"<<endl;
}
void ipTrans(bool m[maxn])
{
    bool cm[maxn];
    int s[] = {58, 60, 62, 64, 57, 59, 61, 63};
    for(int i = 0, l = 1; i < 8; i++) {
        for(int j = s[i]; j > 0; j -= 8) {
            cm[l++] = m[j];
        }
    }
    for(int i = 1; i <= 64; i++) {
        m[i] = cm[i];
    }
}
void PC_1(bool k[maxn])
{
    bool ck[maxn];
    int st[] = {57, 58, 59, 60, 63, 62, 61, 28};
    int le[] = {8, 8, 8, 4, 8, 8, 8, 4};
    for(int i = 0, l = 1; i < 7; i++) {
        for(int j = 0; j < le[i]; j++) {
            ck[l++] = k[st[i] - j * 8];
        }
    }
    for(int i = 0; i <= 56; i++) {
        k[i] = ck[i];
    }
}
int cirMv[] = {1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
void circle_left(bool k[maxn], int t)
{
    t = cirMv[t];
    bool C[maxn >> 1], D[maxn >> 1];
    for(int i = 1; i <= 28; i ++) {
        C[i] = k[i], D[i] = k[28 + i];
    }
    for(int j = 0; j < t; j++) {
        for(int i = 0; i < 28; i++) {
            C[i] = C[i + 1], D[i] = D[i + 1];
        }
        C[28] = C[0], D[28] = D[0];
    }
    for(int i = 1; i <= 28; i++) {
        k[i] = C[i], k[28 + i] = D[i];
    }
}
void PC_2(bool k[maxn], bool ck[maxn])
{
    int transTable[] = {
        14, 17, 11, 24, 1, 5,
        3, 28, 15, 6, 21, 10,
        23, 19, 12, 4, 26, 8,
        16, 7, 27, 20, 13, 2,
        41, 52, 31, 37, 47, 55,
        30, 40, 51, 45, 33, 48,
        44, 49, 39, 56, 34, 53,
        46, 42, 50, 36, 29, 32
    };
    for(int i = 0; i < 48; i++) {
        ck[i + 1] = k[transTable[i]];
    }
}
const int selectMatrix[8][4][16] = {
    // S1
    14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
    0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
    4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
    15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
    //S2
    15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
    3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
    0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
    13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
    //S3
    10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
    13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
    13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
    1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
    //S4
    7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
    13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
    10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
    3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
    //S5
    2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
    14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
    4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
    11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
    //S6
    12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
    10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
    9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
    4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
    //S7
    4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
    13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
    1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
    6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
    //S8
    13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
    1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
    7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
    2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11
};
void encrypt_f(bool R[maxn], bool k[maxn], bool fR[maxn])
{
    bool ER[maxn], p[maxn];
    int st[] = {0, 4, 8, 12, 16, 20, 24, 28};
    for(int i = 0, l = 1; i < 8; i++) {
        for(int j = 0; j < 6; j++) {
            ER[l++] = R[st[i] + j];
        }
    }
    ER[1] = R[32], ER[48] = R[1];
    for(int i = 1; i <= 48; i++) {
        ER[i] = ER[i] ^ k[i];
    }
    for(int i = 0, l = 1; i < 8; i++) {
        int locbit[10], row, column;
        for(int j = 1; j <= 6; j++) {
            locbit[j] = ER[i * 6 + j];
        }
        row = (locbit[1] << 1) | locbit[6];
        column = 0;
        for(int j = 2; j <= 5; j++) {
            column |= (int)locbit[j] << (5 - j);
        }
        int res = selectMatrix[i][row][column];
        for(int i = 3; i >= 0; i--) {
            p[l++] = (res & (1 << i)) ? 1 : 0;
        }
    }
    int p_trans[] = {
        16, 7, 20, 21,
        29, 12, 28, 17,
        1, 15, 23, 26,
        5, 18, 31, 10,
        2, 8, 24, 14,
        32, 27, 3, 9,
        19, 13, 30, 6,
        22, 11, 4, 25
    };
    for(int i = 0; i < 32; i++) {
        fR[i + 1] = p[p_trans[i]];
    }
}
void re_ipTrans(bool m[maxn])
{
    bool cm[maxn];
    int st[] = {40, 8, 48, 16, 56, 24, 64, 32};
    for(int i = 0, l = 1; i < 8; i++) {
        for(int j = 0; j < 8; j++) {
            cm[l++] = m[st[j] - i];
        }
    }
    for(int i = 1; i <= 64; i++) {
        m[i] = cm[i];
    }
}
int main()
{
    bool m[maxn], k[maxn], ck[maxn];
    int n = 64;
    char in[6];
    freopen("data.in", "r", stdin);
    for(int i = 0, l = 1; i < 16; i++) {
        cin >> in;
        for(int j = 0; j < 4; j++) {
            m[l++] = in[j] - '0';
        }
    }
    for(int i = 0, l = 1; i < 16; i++) {
        cin >> in;
        for(int j = 0; j < 4; j++) {
            k[l++] = in[j] - '0';
        }
    }
    // 初始置换IP
    ipTrans(m);
    bool L[maxn >> 1], R[maxn >> 1], cR[maxn >> 1];
    for(int i = 1; i <= 32; i++) {
        L[i] = m[i], R[i] = m[32 + i];
    }
    PC_1(k);
    for(int i = 0; i < 16; i++) {
        // 子密钥生成
        circle_left(k, i);
        PC_2(k, ck);
        // 加密函数f
        encrypt_f(R, ck, cR);
        //获得新的L和R
        for(int j = 1; j <= 32; j++) {
            cR[j] ^= L[j];
        }
        for (int j = 1; j <= 32; j++) {
            L[j] = R[j];
            R[j] = cR[j];
        }
        if(i == 0) {
            cout << "L = "; output(L, 32);
            cout << "R = "; output(R, 32);
        }
    }
    for(int i = 1; i <= n / 2; i++) {
        m[i] = R[i], m[i + 32] = L[i];
    }
    re_ipTrans(m);
    output(m, 64);
    return 0;
}

求得

L = 1101 0110 1010 0101 0010 0101 1000 1000
R = 1010 0110 0001 0100 0011 1001 1100 0100

IDEA

[2]

已知IDEA密码算中:

明文 m =

01011100 10001101 10101001 11011110
10101101 00110101 00010011 10010011

密钥 K =

00101001 10101100 11011000 11100111
10100101 01010011 10100010 01011001
00101000 01011001 11001010 11100111
10100010 00101010 11010101 00110101

求第一轮的输出与第二轮的输入。

得到第一轮的输出(first iteration's output) :

0111 1111 0111 1001
1001 1001 0101 1101
0110 0000 0110 0011
0010 0101 0001 0100

以及第二轮的输入(second iteration's input) :

m =
0111 1111 0111 1001
1001 1001 0101 1101
0110 0000 0110 0011
0010 0101 0001 0100
z(1 - 6) =
1010 0010 0010 1010
1101 0101 0011 0101
1100 1111 0100 1010
1010 0111 0100 0100
1011 0010 0101 0000
1011 0011 1001 0101

[3]

已知IDEA密码算中:

$$Z_1^{(1)} = 1000010010011101$$
求 $[Z_1^{(1)}]^{-1}$ 与 $- Z_1^{(1)}$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
// 快速幂乘
LL ksPower(LL a, LL n, LL p)
{
    LL ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
// 费马小定理求乘法逆元
LL getReverse(LL a, LL p)
{
    return ksPower(a, p - 2, p);
}
void output(LL d)
{
    for(int i = 15; i >= 0; i--) {
        if(d & (1 << i)) cout << '1';
        else cout << '0';
    }
    cout << endl;
}
int main()
{
    char z[20];
    cin >> z;
    LL d = 0, p = (1 << 16) + 1;
    for(int i = 0; i < 16; i++) {
        if(z[i] == '1') {
            d |= 1LL << (15 - i);
        }
    }
    cout << "addition reverse : ";
    output(p - 1 - d);
    cout << "multiplication reverse : ";
    output(getReverse(d, p));
    return 0;
}

求得 :

addition reverse : 0111101101100011
multiplication reverse : 1011000000110011

FEAL

[4]

已知FEAL密码中
明文 m=

0011 1010 1101 0111 0010 1010 1100 0010
1101 0111 1011 1000 0101 1101 0100 1000

密钥 K=

1001 0010 1001 0010 1111 1000 0110 0001
1101 0101 0011 1000 0100 1000 1101 1110

求L0与R0。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned char usch;
const int maxn(10);
void input(usch *s)
{
    # define anlsget(g, sig) do{\
        usch d = 0, x[5];\
        cin >> x;\
        for(int j = 0; j < 4; j++) {\
            if(x[j] - '0') d |= 1 << (3 - j);\
        }\
        g |= (sig ? d << 4 : d);\
    }while(false)
     for(int i = 0; i < 8; i++) {
        s[i] = 0;
        anlsget(s[i], 1);
        anlsget(s[i], 0);
     }
}
void output(usch *s, int l)
{
    for(int i = 0; i < l; i++) {
        for(int j = 0; j < 8; j++) {
            cout << ((s[i] & (1 << (7 - j))) ? 1 : 0);
            if(((j + 1) & 3) == 0) cout << ' ';
        }
    }
    cout << endl;
    puts("----------------------");
}
usch S(usch x1, usch x2, int sigm)
{
    usch w = (sigm + x1 + x2) % (1 << 8);
    return (w << 2) | (w >> 6);
}
void f_K(usch *a, usch *b, usch *f)
{
    usch h1 = a[1] ^ a[0];
    usch h2 = a[3] ^ a[2];
    f[1] = S(h1, h2 ^ b[0], 1);
    f[2] = S(h2, f[1] ^ b[1], 0);
    f[0] = S(a[0], f[1] ^ b[2], 0);
    f[3] = S(a[3], f[2] ^ b[3], 1);
}
void product_sub_key(usch *key, usch K[][2])
{
    usch A[4], B[4];
    memcpy(A, key, 4);
    memcpy(B, key + 4, 4);
    usch D[4], cB[4];
    for(int i = 0; i < 6; i++) {
        memcpy(D, A, 4);
        memcpy(A, B, 4);
        for(int j = 0; j < 4; j++) {
            cB[i] = B[i] ^ D[i];
        }
        f_K(D, cB, B);
        memcpy(K[i * 2], B, 2);
        memcpy(K[i * 2 + 1], B + 2, 2);
    }
}
void encrypt_f(usch a[4], usch b[2], usch f[4])
{
    usch g1 = a[1] ^ b[0] ^ a[0];
    usch g2 = a[2] ^ b[1] ^ a[3];
    f[1] = S(g1, g2, 1);
    f[2] = S(g2, f[1], 0);
    f[3] = S(a[3], f[1], 1);
    f[0] = S(a[0], f[1], 0);
}
void initialize_calculate(usch plx[8], usch L[4], usch R[4], usch K[12][2])
{
    memcpy(L, plx, 4);
    memcpy(R, plx + 4, 4);
    for(int i = 0; i < 2; i++) {
        L[i] ^= K[4][i];
        L[i + 2] ^= K[5][i];
        R[i] ^= K[6][i];
        R[i + 2] ^= K[7][i];
    }
    for(int i = 0; i < 4; i++) {
        R[i] ^= L[i];
    }
}
void iteration(usch L[4], usch R[4], int j, usch K[12][2])
{
    usch f[4], cL[4];
    memcpy(cL, L, 4);
    memcpy(L, R, 4);
    encrypt_f(R, K[j], f);
    for(int i = 0; i < 4; i++) {
        R[i] = cL[i] ^ f[i];
    }
}
void tail_calculate(usch L[4], usch R[4], usch ctx[maxn], usch K[12][2])
{
    for(int i = 0; i < 4; i++) {
        R[i] ^= L[i];
    }
    for(int i = 0;  i < 2; i++) {
        R[i] = R[i] ^ K[8][i];
        R[i + 2] = R[i + 2] ^ K[9][i];
        L[i] = L[i] ^ K[10][i];
        L[i + 2] = L[i + 2] ^ K[11][i];
    }
    for(int i = 0; i < 4; i++) {
        ctx[i] = R[i];
        ctx[i + 4] = L[i];
    }
}
int main()
{
    freopen("data.in", "r", stdin);
    usch plaintext[maxn], key[maxn], ciphertext[maxn];
    input(plaintext);
    input(key);
    usch sub_key[12][2], L[4], R[4];
    product_sub_key(key, sub_key);
    initialize_calculate(plaintext, L, R, sub_key);
    cout << "L = "; output(L, 4);
    cout << "R = "; output(R, 4);
    for(int i = 0; i < 4; i++) {
        iteration(L, R, i, sub_key);
    }
    tail_calculate(L, R, ciphertext, sub_key);
    output(ciphertext, 8);
    return 0;
}

求得 :

L = 1000 1000 0110 0000 1011 0100 0000 1100
R = 0000 1000 0000 0101 0111 0110 0000 1110

[5]

已知 a, b 分别为

a = 10000011 11010111 10100101 00110100
b = 00101011 10011010 00100101 11011100

$f_K$ 为FEAL密码的子密钥产生函数，求 $f_K(a, b)$

usch S(usch x1, usch x2, int sigm)
{
    usch w = (sigm + x1 + x2) % (1 << 8);
    return (w << 2) | (w >> 6);
}
void f_K(usch a[4], usch b[4], usch f[4])
{
    usch h1 = a[1] ^ a[0];
    usch h2 = a[3] ^ a[2];
    f[1] = S(h1, h2 ^ b[0], 1);
    f[2] = S(h2, f[1] ^ b[1], 0);
    f[0] = S(a[0], f[1] ^ b[2], 0);
    f[3] = S(a[3], f[2] ^ b[3], 1);
}

求得结果为 :

f = 01110010 00111100 11011100 11010100

[6]

已知

α = 00101011 11011101 10000001 01001000
β = 10011101 11100111

$f$ 为FEAL密码的加密函数，求 $f(a, b)$。

usch S(usch x1, usch x2, int sigm)
{
    usch w = (sigm + x1 + x2) % (1 << 8);
    return (w << 2) | (w >> 6);
}
void encrypt_f(usch a[4], usch b[2], usch f[4])
{
    usch g1 = a[1] ^ b[0] ^ a[0];
    usch g2 = a[2] ^ b[1] ^ a[3];
    f[1] = S(g1, g2, 1);
    f[2] = S(g2, f[1], 0);
    f[3] = S(a[3], f[1], 1);
    f[0] = S(a[0], f[1], 0);
}

求得 :

f = 01010110 01101010 01100010 11001110

欧几里得算法（拓展gcd）

[1]

用欧几里得算法求 $67(mod 119)$ 的逆元。

#include <bits/stdc++.h>
using namespace std;
void exgcd(int a, int b, int &x, int &y)
{
    if(!b) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= x * (a / b);
}
int main()
{
    int a, b, x, y;
    cin >> a >> b;
    exgcd(a, b, x, y);
    cout << x << endl;
}

求得逆元为 : 16

线性同余式

[2]

求解下列线性同余式

• $11x = 28 (mod 37)$
• $42x = 90 (mod 156)$

#include <bits/stdc++.h>
using namespace std;
void exgcd(int a, int b, int &d, int &x, int &y)
{
    if(!b) {
        d = a, x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, d, y, x);
    y -= x * (a / b);
}
int main()
{
    int a, b, c, x, y, d;
    // ax = c (mod b)
    cin >> a >> c >> b;
    exgcd(a, b, d, x, y);
    if(c % d != 0) {
        cout <<"no solution";
    }
    else {
        x = (x * (c / d)) % b;
        cout << (x + b) % b;
    }
    cout << endl;
    return 0;
}

求得上两式的解分别为 : 16 和 147

[3]

求解下列同余方程组

$$\left\{ \begin{aligned} x = 2(mod \ 3) \\ x = 1(mod \ 5)\\ x = 1(mod \ 7) \end{aligned} \right. \text{和} \left\{ \begin{aligned} x = &7(mod \ 9) \\ x = &0(mod \ 10)\\ x = &3(mod \ 7) \end{aligned} \right.$$

#include <bits/stdc++.h>
using namespace std;
// 拓展欧几里得
int exgcd(int a, int b, int &x, int &y)
{
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}
// 中国剩余定理
int china(int *b, int *w, int k)
{
    int i, d, x, y, m, a = 0, n = 1;
    for(i = 0; i < k; i++) {
        n *= w[i];
    }
    for(i = 0; i < k; i++) {
        m = n / w[i];
        d = exgcd(w[i], m, x, y);
        a = (a + y * m * b[i]) % n;
    }
    if(a > 0) return a;
    else return a + n;
}
int main()
{
    const int maxn(5);
    int a[maxn], b[maxn], n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    cout << china(a, b, n) << endl;
    return 0；
}

求得两个方程组的解分别为 : 71 和 430

快速幂乘

[4]

求 $3^{372} = ? \ (mod \ 37)$

// a^n % mod = ans
int quickPower(int a, int n, int mod)
{
    int ans = 1;
    while(n) {
        if(n & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

求得结果为 : 33

RSA公钥密码

[5]

已知RSA密码体制的公开钥为 $n = 2881, e = 13$，试对明文best wisheas加密。

#include <bits/stdc++.h>
using namespace std;
// 快速幂乘
int quicksPower(int a, int n, int mod)
{
    int ans = 1;
    while(n) {
        if(n & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
// 加密函数
int encrypt(char a[2], int e, int n)
{
    int d = a[0] - 'a';
    if(a[1] >= 'a' && a[1] <= 'z') {
        d = d * 100 + a[1] - 'a';
    }
    return quicksPower(d, e, n);
}
int main()
{
    freopen("data.in", "r", stdin);
    const int maxn(20);
    char plaintext[maxn];
    gets(plaintext);
    for(int i = 0, j = 0; plaintext[i]; i++) {
        if(plaintext[i] >= 'a' && plaintext[i] <= 'z') {
            plaintext[j++] = plaintext[i];
        }
    }
    int e, n;
    scanf("%d%d", &n, &e);
    for(int i = 0; plaintext[i]; i += 2) {
        int ciphertext = encrypt(plaintext + i, e, n);
        printf("%04d ", ciphertext);
    }
    puts("");
    return 0;
}

求得相应的密文为 : 0975 1694 0009 2796 0255

背包公钥

[6]

已知背包公钥系统的超递增序列为 $(3, 4, 9, 17, 35)$ ，乘数 $w = 19$，模数 $m = 73$，试对明文 good night 进行加密。

#include <bits/stdc++.h>
using namespace std;
// 获得b序列
void get_bs(int *a, int *b, int n, int w, int m)
{
    for(int i = 0; i < n; i++) {
        b[i] = a[i] * w % m;
    }
}
// 进行单个字符的加密
int encrypt(int *b, char c, int n)
{
    int d = c - 'a', ciphertext = 0;
    for(int i = 0; i < n; i++) {
        int j = 1 << (n - i - 1);
        if(d & j) {
            ciphertext += b[i];
        }
    }
    return ciphertext;
}
int main()
{
    freopen("data.in", "r", stdin);
    const int maxn(20);
    int a[maxn], b[maxn], w, m, n;
    char plaintext[maxn];
    gets(plaintext);
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    scanf("%d%d", &w, &m);
    get_bs(a, b, n, w, m);
    for(int i = 0; plaintext[i]; i++) {
        if(plaintext[i] < 'a' || plaintext[i] > 'z') {
            continue;
        }
        printf("%d ", encrypt(b, plaintext[i], n));
    }
    puts("");
    return 0;
}

求得密文为 : 56 59 59 39 36 3 56 64 96

[7]

已知背包公钥系统的超递增序列为 $(3, 4, 8, 17, 33)$ ，乘数 $w = 17$，模数 $m = 67$，试对密文 $25，2，72，92$ 进行解密。

#include <bits/stdc++.h>
using namespace std;
const int maxn(10);
int femat(int w, int n)
{
    int m = n - 2, ans = 1;
    while(m) {
        if(m & 1) ans = ans * w % n;
        w = w * w % n;
        m >>= 1;
    }
    return ans;
}
int decode(int rw, int c, int *a, int m, int n)
{
    int d = rw * c % m, ans = 0;
    for(int i = n - 1; i >= 0; i--) {
        if(d >= a[i]) {
            ans += (1 << (n - 1 - i));
            d -= a[i];
        }
    }
    return ans;
}
int main()
{
    int n, a[maxn], w, m;
    int ciphertext[maxn];
    freopen("data.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    scanf("%d%d", &w, &m);
    int j = 0;
    while(~scanf("%d", ciphertext + j)) {
        j++;
    }
    int rw = femat(w, m);
    for(int i = 0; i < j; i++) {
        char plaintext = 'a' + decode(rw, ciphertext[i], a, m, n);
        cout << plaintext;
    }
    puts("");
    return 0;
}

解得明文为 : besb

香农理论

[1]

设明文空间共含有5个信息 $m_i(1 \leq u \leq 5)$，并且

$$P(m_1) = P(m_2) = \frac 1 4, P(m_3) = \frac 1 8, P(m_4) = P(m_5) = \frac 3 {16}$$
求 $H(M)$

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from math import log
Pm = [1/4, 1/4, 1/8, 3/16, 3/16]
Hm = sum(map(lambda x : -x * log(x, 2), Pm))
print (Hm)

得到结果为 : 2.2806390622295662

[2]

考虑一个密码体制 $M = \{a, b, c\}$， $K = \{k_1, k_2, k_3\}$ 和 $C = \{1, 2, 3, 4\}$ 。假设加密矩阵为

	a	b	c
$k_1$	2	3	4
$k_2$	3	4	1
$k_3$	1	2	3

已知密钥概率分布

$$P(k_1) = P(k_2) = \frac 1 4， P(k_3) = \frac 1 2$$ 明文概率分布为 $$P(a) = \frac 1 3, P(b) = \frac 1 4, P(c) = \frac 5 {12}$$ 计算 $$H(M), H(K), H(C), H(M/C), H(K/C)$$

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from math import log
def entropy(p) :
    return -p * log(p, 2)
'''
Pk = [1/4, 1/4, 1/2]
Pm = [1/3, 1/4, 5/12]
epMatrix = [[2, 3, 4], [3, 4, 1], [1, 2, 3]]
'''
Pk = [1/2, 1/4,1/4]
Pm = [1/4, 3/4]
epMatrix = [[1, 2], [2, 3], [3, 4]]
Hm = sum(map(entropy, Pm))
print ("H(M) =", Hm)
Hk = sum(map(entropy, Pk))
print ("H(K) =", Hk)
cTomk, objNum = {}, 0
for k, row in enumerate(epMatrix) :
    for m, code in enumerate(row) :
        if code not in cTomk :
            cTomk[code] = []
        cTomk[code].append((k, m, Pk[k] * Pm[m]))
        objNum += 1
Pc = [sum(map(lambda x: x[2], cTomk[cmk])) for cmk in cTomk]
Hc = sum(map(entropy, Pc))
print ("H(C) =", Hc)
Hmc, Hkc = 0, 0
for (p, cmk) in zip(Pc, cTomk) :
    Pmc, Pkc = {}, {}
    for (k, m, pkm) in cTomk[cmk] :
        Pmc[m] = Pmc.setdefault(m, 0) + pkm
        Pkc[k] = Pkc.setdefault(k, 0) + pkm
    for m in Pmc :
        Hmc += p * entropy(Pmc[m] / p)
    for k in Pkc :
        Hkc += p * entropy(Pkc[k] / p)
print ("H(M/C) =", Hmc)
print ("H(K/C) =", Hkc)
print ("H(K/C) = H(M) + H(K) - H(C) =", Hk + Hm - Hc)

求得 :

H(M) = 1.5545851693377997
H(K) = 1.5
H(C) = 1.9430486343469147
H(M/C) = 1.1115365349908848
H(K/C) = 1.1115365349908848
H(K/C) = H(M) + H(K) - H(C) = 1.111536534990885

[3]

证明： $H(X, Y, Z) = H(X, Y) + H(Z | (X, Z))$

已知概率关系

$$P(X, Y) = P(Y) * P(X|Y)$$ 和
$$H(X, Y) = H(Y) + H(X|Y)$$ 之间存在映射关系
映射关系证明如下 :
对于任意的 $X, Y$都有 $$P(X, Y) = P(Y) * P(X|Y)$$
由上，可以有推导过程 :
$$\begin{split} H(X, Y) =& -\sum_Y \sum_XP(X, Y)log_2(P(X, Y)) \\ \\ =& -\sum_Y\sum_X P(Y)P(X|Y)log_2(P(Y)P(X|Y)) \\ \\ =& -\sum_Y\sum_X P(Y)P(X|Y)log_2(P(Y)P(X|Y)) \\ \\ =& -\sum_Y\sum_X P(Y)P(X|Y)(log_2(P(Y)) + log_2(P(X|Y))) \\ \\ =& -\sum_Y\sum_X P(Y)P(X|Y)log_2(P(Y)) - \sum_Y\sum_X P(Y)P(X|Y)log_2(P(X|Y)) \\ \\ =& \sum_YP(Y)log_2(P(Y))\sum_XP(X|Y) - \sum_Y\sum_X P(Y)P(X|Y)log_2(P(X|Y)) \\ \\ = & -\sum_YP(Y)log_2(P(Y)) - \sum_Y\sum_X P(Y)P(X|Y)log_2(P(X|Y)) \\ \\ =& H(Y) + H(X|Y) \end{split}$$
因此任意$H(X, Y)$ 均可通过上述推导过程由条件 $$P(X, Y) = P(Y) * P(X|Y)$$ 得到 $$H(X, Y) = H(Y) + H(X, Y)$$
即两式之间存在映射
且现已知 $$P(X, Y, Z) = P(X, Y) * P(Z | (X, Y))$$
由映射关系可得 $$H(X, Y, Z) = H(X, Y) + H(Z| (X, Y))$$

[4]

证明一个密码体制完全保密的充要条件为 $H(M|C) = H(M)$

• 必要性证明 ：

  由定理6.5，密码体制完全保密的充要条件是

  $$P(C|M) = P(C)$$
  由概率乘法定理， $$P(C)P(M|C) = P(M)P(C|M)$$
  则可得 $$P(M|C) = P(M)$$
  因此，
  $$\begin{split} H(M|C) =& -\sum_c\sum_mP(C)P(M|C)log_2(P(M|C)) \\ \\ =& -\sum_c\sum_mP(C)P(M)log_2(P(M)) \\ \\ =& -\sum_cP(C) * \sum_mP(M)log_2(P(M)) \\ \\ =& -1 * \sum_mP(M)log_2(P(M)) \\ \\ =& -\sum_mP(M)log_2(P(M)) \\ \\ =& H(M) \end{split}$$
  必要性 得证

• 充分性证明

  $$\begin{split} H(M) =& -\sum_mP(M)log_2(P(M)) \\ \\ =& -1 * \sum_mP(M)log_2(P(M)) \\ \\ =& -\sum_cP(C) * \sum_mP(M)log_2(P(M)) \\ \\ =& -\sum_c\sum_mP(C)P(M)log_2(P(M)) \\ \\ \end{split}$$
  又有
  $$\begin{split} H(M|C) =& -\sum_c\sum_mP(C)P(M|C)log_2(P(M|C)) \end{split}$$
  由上述两式综合可得
  $$P(M)log_2(P(M)) = P(M|C)log_2(P(M|C))$$
  因此
  $$P(M) = P(M|C)$$
  由概率乘法定理 $P(M)*P(C|M) = P(C)*P(M|C)$可得到：
  $$P(C) = P(C|M)$$
  由定理6.3可知当$H(M|C) = H(M)$ 时， 该密码体制是完全保密的
  充分性得证

移位寄存器

[1]

3级线性反馈移位寄存器 $c_3 = 1$时可有4种线性反馈函数，设初态为 $(a_3a_2a_1) = (101)$, 求各线性反馈函数的输出序列和周期。

#include <bits/stdc++.h>
using namespace std;
int f(int *a, int *c, int n)
{
    int g = a[0];
    a[n] = 0;
    for(int i = 0; i < n; i++) {
        a[n] ^= a[i] * c[n - 1 - i];
    }
    for(int i = 0; i < n; i++) {
        a[i] = a[i + 1];
    }
    return g;
}
bool cmp(int *a, int *b, int n)
{
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) return false;
    }
    return true;
}
int main()
{
    int a[5] = {1, 0, 1, 0, 0};
    int c[5] = {0, 0, 1, 0, 0};
    int fa[5], t;
    memcpy(fa, a, sizeof a);
    for(int &i = c[0]; i < 2; i++) {
        c[1] = 0;
        for(int &j = c[1]; j < 2; j++) {
            cout <<"c1 = " << i << ", c2 = " << j << " : " <<endl;
            cout << "output sequence : ";
            t = 0;
            do {
                cout << f(a, c, 3);
                t++;
            }while(!cmp(a, fa, 3));
            cout << endl;
            cout << "period = " << t << endl << endl;
        }
    }
    return 0;
}

由上述程序可得结果 :

c1 = 0, c2 = 0 :
output sequence : 101
period = 3

c1 = 0, c2 = 1 :
output sequence : 1011100
period = 7

c1 = 1, c2 = 0 :
output sequence : 1010011
period = 7

c1 = 1, c2 = 1 :
output sequence : 10
period = 2

[2]

4级线性反馈移位寄存器在 $c_4 = 1$， 可有8种线性反馈函数，设初态为$(a_4a_3a_2a_1) = (1011)$，确定这些线性反馈函数中哪一个将给出周期为 $2^4 - 1$ 的密钥流。

#include <bits/stdc++.h>
using namespace std;
int f(int *a, int *c, int n)
{
    int g = a[0];
    a[n] = 0;
    for(int i = 0; i < n; i++) {
        a[n] ^= a[i] * c[n - 1 - i];
    }
    for(int i = 0; i < n; i++) {
        a[i] = a[i + 1];
    }
    return g;
}
bool cmp(int *a, int *b, int n)
{
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) return false;
    }
    return true;
}
void output(int *a, int n)
{
    while(n--) {
        cout << a[n];
    }
    cout << endl;
}
int main()
{
    int a[] = {1, 1, 0, 1, 0};
    int c[] = {0, 0, 0, 1, 0};
    int fa[5], t;
    memcpy(fa, a, sizeof a);
    for(int &i = c[0]; i < 2; i++) {
        c[1] = 0;
        for(int &j = c[1]; j < 2; j++) {
            c[2] = 0;
            for(int &k = c[2]; k < 2; k++) {
                int t = (1 << 4) - 1;
                do{
                    f(a, c, 4);
                    t--;
                }while(!cmp(a, fa, 4));
                if(!t) {
                    cout << "c = ";
                    output(c, 4);
                }
            }
        }
    }
    return 0;
}

求得两解 :

c = 1100
c = 1001

[3]

[3] 假设破译者得到密文串 $1010110110$ 和相应的明文串 $0100010001$。假定攻击者也知道密钥流是使用3级线性移位寄存器产生的，试破译该密码系统。

#include <bits/stdc++.h>
using namespace std;
int f(int *a, int *c, int n)
{
    int g = a[0];
    a[n] = 0;
    for(int i = 0; i < n; i++) {
        a[n] ^= a[i] * c[n - 1 - i];
    }
    for(int i = 0; i < n; i++) {
        a[i] = a[i + 1];
    }
    return g;
}
void output(int *a, int n)
{
    while(n--) {
        cout << a[n];
    }
    cout << endl;
}
void putIntoArray(int *a, int d, int n)
{
    for(int i = 0; i < 3; i++) {
        a[i] = (d >> i & 1);
    }
}
int main()
{
    char plx[20], ctx[20];
    int a[5] = {0}, c[5] = {0}, fa[5], key[20], l;
    //输入 plx = '0100010001', ctx = '1010110110'
    cin >> plx >> ctx;
    l = strlen(plx);
    for(int i = 0; i < l; i++) {
        key[i] = (plx[i] - '0') ^ (ctx[i] - '0');
    }
    for(int i = 0; i < (1 << 3); i++) {
        for(int j = 0; j < (1 << 3); j++) {
            putIntoArray(c, j, 3);
            putIntoArray(a, i, 3);
            int k = 0;
            for(k = 0; k < l; k++) {
                if(key[k] != f(a, c, 3)) break;
            }
            if(k >= l) {
                cout << "a = "; output(a, 3);
                cout << "c = "; output(c, 3);
                return 0;
            }
        }
    }
    puts("no solution");
    return 0;
}

解得 :

a = 010
c = 101

[4]

设 $n = 4, f(a_1, a_2, a_3, a_4) = a_1 \oplus a_4 \oplus 1 \oplus a_2a_3$ 初态为 $(a_4a_3a_2a_1) = (1011)$，试求此非线性移位寄存器的输出序列及周期。

#include <bits/stdc++.h>
using namespace std;
int f(int *a)
{
    int g = a[1];
    a[5] = a[1] ^ a[4] ^ 1 ^ (a[2] * a[3]);
    for(int i = 1; i <= 4; i++) {
        a[i] = a[i + 1];
    }
    return g;
}
bool cmp(int *a, int *b)
{
    for(int i = 1; i <= 4; i++) {
        if(a[i] != b[i]) return false;
    }
    return true;
}
int main()
{
    int a[] = {0, 1, 1, 0, 1, 0}, fa[6];
    int t = 0;
    memcpy(fa, a, sizeof a);
    cout << "sequence = ";
    do {
        cout << f(a);
        t ++;
    }while(!cmp(a, fa));
    cout << endl;
    cout <<"period = " << t << endl;
    return 0;
}

解得 :

sequence = 11011
period = 5

[5]

[5] 设J-K触发器中$\{a_i\}$ 是3级m序列， $\{b_i\}$是4级m序列，且

$$\begin{split} \{a_i\} =& 11101001110100 \\ \{b_i\} =& 001011011011000001011011011000 \end{split}$$
试求J-K触发器的输出序列$\{u_i\}$ 及周期。

#include <bits/stdc++.h>
using namespace std;
const int maxn(50);
int input(int *d)
{
    char cd[maxn];
    cin >> cd;
    int ld = strlen(cd);
    for(int i = 1, j, k; i < ld; i++) {
        if(ld % i != 0) continue;
        for(j = 0, k; j < i; j++) {
            for(k = j; k < ld; k += i) {
                if(cd[k] != cd[j]) break;
            }
            if(k < ld) break;
        }
        if(j >= i) {
            ld = i;
            break;
        }
    }
    for(int i = 0; i < ld; i++) {
        d[i] = cd[i] - '0';
    }
    return ld;
}
int main()
{
    freopen("data.in", "r", stdin);
    int a[maxn], am, b[maxn], bn, u = 0;
    am = input(a);
    bn = input(b);
    for(int i = 0; i < bn; i++) {
        b[i] = 1 - b[i];
    }
    int j = 0, fu = a[0] == b[0] ? -1 : 1;
    do {
        u = u ? b[j % bn] : a[j % am];
        j++;
        cout << u;
        if(j % 15 == 0) cout <<endl;
    }while(j % am != 0 || j % bn != 0);
    cout << endl;
    cout << "period = " << j << endl;
    return 0;
}

得到结果为 :

110010010101111
110100101100011
110001100100111
110010101101111
110101100010111
110100100101111
110101101100111

period = 105

[6]

[6] 设二元域GF(2)上的一个线性移位寄存器的联系多项式为$f(x) = 1 + x + x^3 + x^4$，初始状态为 $1101$，试求其输出序列及其周期。

#include <bits/stdc++.h>
using namespace std;
const int maxn(20);
int input(int *a)
{
    char s[maxn];
    cin >> s;
    int i;
    for(i = 0; s[i]; i++) {
        a[i] = s[i] - '0';
    }
    return i;
}
int f(int *a, int *c, int n)
{
    int g = a[0];
    a[n] = 0;
    for(int i = 0; i < n; i++) {
        a[n] += a[i] * c[i];
    }
    a[n] &= 1;
    for(int i = 0; i < n; i++) {
        a[i] = a[i + 1];
    }
    return g;
}
bool cmp(int *a, int *fa, int n)
{
    for(int i = 0; i < n; i++) {
        if(a[i] != fa[i]) return false;
    }
    return true;
}
int main()
{
    int n;
    int c[maxn], a[maxn], fa[maxn];
    cin >> n;
    input(c);
    input(a);
    memcpy(fa, a, sizeof a);
    int t = 0;
    do {
        cout << f(a, c, n);
        t++;
    }while(!cmp(a, fa, n));
    cout << endl;
    cout  << "period = " << t << endl;
    return 0;
}

求得 :

1101000
period = 7

[7]

设二元域GF(2)上的一个线性移位寄存器的联系多项式为 $f(x) = 1 + x + x^2 + x^3 + x^5$，初始状态为 $(01101)$，试求其输出序列及其周期.

由[6]的程序可求得 :

0110111110100010010101100001110
period = 31

数字签名

[1]

在DSS数字签名标准中，取 $p = 83 = 2 * 41 + 1, q = 41$, $2$ 是 $(mod \ 83)$的一个本原元，于是 $g = 2^2 = 4 (mod \ 83)$，若取 $x = 57$，则 $y = g^x = 4^{57} = 77(mod \ 83)$，假设想签名一个消息 $m = 56$，且选择 $k = 23$，计算明文 $m = 56$ 的签名，然后验证。

#include <bits/stdc++.h>
using namespace std;
int quickPower(int a, int n, int mod)
{
    int ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
//83 41 23 4 56 57 77
int main()
{
    int p, q, k, g, x, m, y;
    cout <<"input p, q, k, g, m, x, y :" << endl;
    cin >> p >> q >> k >> g >> m >> x >> y;
    int r = quickPower(g, k, p) % q;
    cout << "r = " << r << endl;
    int rk;
    for(rk = 1; rk < q; rk++) {
        if(rk * k % q == 1) break;
    }
    int s = (rk * (m + x * r)) % q;
    cout << "s = " << s << endl;
    cout <<"------------" << endl;
    int rs = 0;
    while(rs * s % q != 1) rs++;
    int w = rs % q;
    cout << "w = " << w << endl;
    int u1 = (m * w) % q;
    cout << "u1 = " << u1 << endl;
    int u2 = (r * w) % q;
    cout << "u2 = " << u2 << endl;
    int v = quickPower(g, u1, p) * quickPower(y, u2, p) % p % q;
    cout << "v = " << v  << endl;
    return 0;
}

由上述程序可得 :

$\begin{split} r =& (g^k \ mod \ p) \ mod \ q \\ \\ =& 10 \end{split}$

$\begin{split} s =& (k^{-1} * (m + x * r))\ mod \ q \\ \\ =& 29 \end{split} \\$
得到密文 $(r, s) = (10, 29)$

验证 ：

$\begin{split} w =& s^{-1} \ mod \ q \\ \\ =& 17 \end{split}$

$\begin{split} u_1 =& (m * w) \ mod \ q \\ \\ =& 9 \end{split}$

$\begin{split} u_2 =& (r * w) \ mod \ q \\ \\ =& 6 \end{split}$

$\begin{split} v =& ((g^{u1} * y^{u2}) \ mod \ p) \ mod \ q \\ \\ =& 10 \end{split} \\$
得到 : v = r, 验证成功

[2]

假设用户A使用了$p = 7879, q = 101, g = 170, x = 75$ 和 $y = 4567$ 的DSS数字签名标准，利用随机值 $k = 43$ 确定关于消息 $m = 3231$ 的用户A签名，且说明产生签名是怎样验证的.

A签名, 由[1]给出的程序计算出 ：

$r = (g^k \ \% \ p) \ \% \ q = 85$

$s = (k^{-1} * (m + x * r)) \ \% \ q = 12$

然后将$(m, r, s)$ 发送给B

B验证， 由[1]给出的程序 ：

$w = s^{-1} \ \% \ q = 59$

$u_1 = (m * w) \ \% \ q = 42$

$u_2 = r * m \ \% \ q = 66$

最后计算出 $v = (g^{u_1} * y^{u_2} \ \% \ p) \ \% \ q = 85$

与r相等， 验证成功，是A的数字签名