作业三

密码学

相关函数的定义

# include<iostream>
using namespace std;
int x, y, d;
int q=0, r=0;
//定义G(2^8)中的 x*2
int mul2(int x){
    if (x&0x80) return ((x << 1) ^ 27)&255;     //&255表示 只取一个字节
    else return (x << 1)&255;
}
//G(2^8)乘法
int mul(int x, int y) {
    int r = 0, tmp = x;
    while (y) {
        if (y % 2) r ^= tmp;     //加法取模相当于亦或
        tmp = mul2(tmp);
        y /= 2;
    }
    return r;
}
//获取最高位1的位置
int hight_index(int x) {
    if (!x) return 0;   //x等于0，返回0。表示不存在最高位的1
    int index = 1;      
    while (x >> 1) {
        x = x >> 1;
        ++index;
    }
    return index;
}
//G(2^n)除法
void divi(int a, int b) {
    int tmp = 0;
    r = 0; q = 0;
    while (b <= a) {
        tmp = 1;
        int indexB = hight_index(b), indexA = hight_index(a);
        int dis = indexA - indexB;
        tmp = tmp << dis;
        q += tmp;
        a = a ^ (tmp*b);
    }
    r = a;
}
//ax + by = d = gcd(a,b), 其中a>b
int egcd(int a, int b) {
    int x1 = 1, y1 = 0, x2 = 0, y2 = 1;
    int tmp_x, tmp_y;
    while(b){
        divi(a, b);
        tmp_x = x2;
        tmp_y = y2;
        x2 = x1^mul(x2,q);    //1式 减去 (2式 * q), 接着轮换系数
        y2 = y1^mul(y2,q);   
        x1 = tmp_x;
        y1 = tmp_y;
        a = b;
        b = r;
    }
    return y1;
}

测试$G(2^n)$乘法

　　通过穷举来判断是否所有的元素都有逆元，从而间接的判断这个算法是不是有问题的。经验证，确实所有的数都存在乘法逆元！
　　

int main() {
    for (int i = 1; i <= 255; ++i) {
        for (int j = 1; j <= 255; ++j) {
            if (mul(i, j) % 283 == 1) {
                cout << i << "的逆元是：" << j << endl;
                break;
            }
        }
    }
    system("pause");
    return 0;
}

测试$egcd$

　　这里用egcd来求出1到255的逆元，并与之前测试乘法所求的逆元相对比。发现两次求得逆元是相同的。或许这样子可以验证egcd算法结果的正确性？？？(我也不知道行不行)

int main() {
    for (int i = 1; i <= 255; ++i)
        cout << i << "的逆元是：" << egcd(283, i) << endl;
    system("pause");
    return 0;
}