阿龙咖啡 /

编写 DES 与 RSA 密码算法

这个学期上信息安全课,期末课程设计是用任意编程语言实现 DES 和 RSA 两个加密 / 解密算法。花了几天时间研究了一下,照着 Wiki 和参考文档用 C++ 写出来了。因为实现比较简单,就不传 Github 了,现在想在博客保存一下代码副本,免得将来丢失了。

DES 加密/解密算法实现

#include <iostream>

/* 循环左移 */
#define ROL(_x_, _b_, _s_) (((_x_) << (_b_)) | ((_x_) >> ((_s_) - (_b_))))

static inline /* 高效求 2 的 p 次方函数 */
uint64_t pow2(int p) {
    if (p == -1) return 0;
    uint64_t ans = 1;
    ans <<= p;
    return ans;
}

static inline /* 置换操作辅助函数 */
uint64_t trans(const uint64_t & src, const char tab[], size_t tabsize, int range) {
    uint64_t obj = 0;
    for (size_t i = 0; i < tabsize; ++i) {
        auto bit = (pow2(range - tab[i]) & src);
        (obj <<= 1) |= (bit ? 1ULL : 0ULL);
    }
    return obj;
}

static inline /* 费斯妥 F 函数 */
uint32_t feistel(uint32_t r, uint64_t k) {
    // 扩展置换
    const static char e[48] = {
        32,  1,  2,  3,  4,  5,
         4,  5,  6,  7,  8,  9,
         8,  9, 10, 11, 12, 13,
        12, 13, 14, 15, 16, 17,
        16, 17, 18, 19, 20, 21,
        20, 21, 22, 23, 24, 25,
        24, 25, 26, 27, 28, 29,
        28, 29, 30, 31, 32,  1
    };

    uint64_t er = trans(r, e, sizeof(e), 32);

    // S 盒替代
    const static char s[8][64] = {
        {
            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
        }, {
            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
        }, {
            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
        }, {
             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
        }, {
             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
        }, {
            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
        }, {
             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
        }, {
            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
        }
    };

    uint64_t s_input = (er ^ k);
    uint32_t s_output = 0;
    for (int i = 7; i >= 0; --i) {
        auto row = ((s_input & 0x01ULL) ? 1 : 0)
            + ((s_input & 0x20ULL) ? 1 : 0) * 2;
        auto col = ((s_input & 0x1eULL) >> 1);
        s_input >>= 6;
        s_output >>= 4;
        s_output |= (s[i][row * 16 + col] << 28);
    }

    // P 盒置换
    const static char p[32] = {
        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
    };

    uint32_t p_output = static_cast<uint32_t>(trans(s_output, p, sizeof(p), 32));

    return p_output;
}

static inline /* DES 核心算法 */
uint64_t des(const uint64_t &m, const uint64_t &key, bool encrypt) {
    /* ******************** 初始置换 ******************** */
    const static char ip[64] = {
        58, 50, 42, 34, 26, 18, 10, 2,
        60, 52, 44, 36, 28, 20, 12, 4,
        62, 54, 46, 38, 30, 22, 14, 6,
        64, 56, 48, 40, 32, 24, 16, 8,
        57, 49, 41, 33, 25, 17,  9, 1,
        59, 51, 43, 35, 27, 19, 11, 3,
        61, 53, 45, 37, 29, 21, 13, 5,
        63, 55, 47, 39, 31, 23, 15, 7
    };

    uint64_t m_ = trans(m, ip, sizeof(ip), 64);

    // 初始子密钥
    uint32_t l[17] = { 0 };
    uint32_t r[17] = { 0 };
    l[0] = ((uint32_t*)&m_)[1];
    r[0] = ((uint32_t*)&m_)[0];

    /* ******************* 生成子密钥 ******************* */
    const static char pc_1[56] /* 1~64 */ = {
        57, 49, 41, 33, 25, 17,  9,
         1, 58, 50, 42, 34, 26, 18,
        10,  2, 59, 51, 43, 35, 27,
        19, 11,  3, 60, 52, 44, 36,
        63, 55, 47, 39, 31, 23, 15,
         7, 62, 54, 46, 38, 30, 22,
        14,  6, 61, 53, 45, 37, 29,
        21, 13,  5, 28, 20, 12,  4
    };

    uint64_t k[17] = { 0 }; /* 0: 56, 1~16: 48 */

    uint64_t &k_ = k[0]; /* 56, 48, 48... */ 
    k_ = trans(key, pc_1, sizeof(pc_1), 64);
    uint32_t c[17], d[17]; /* 28 */
    c[0] = static_cast<uint32_t>((k_ >> 28) & 0x0fffffffULL); // 前 28 位
    d[0] = static_cast<uint32_t>(k_ & 0x0fffffffULL); // 后 28 位
    
    const static char shift[17] = {
        0, /* 保留 */
        1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
    };

    const static char pc_2[48] /* 1~56 */ = {
        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 = 1; i <= 16; ++i) {
        c[i] = ((ROL(c[i - 1], shift[i], 28) & 0xfffffffUL)); // 前 28 位
        d[i] = ((ROL(d[i - 1], shift[i], 28) & 0xfffffffUL)); // 后 28 位
        uint64_t ans = 0;
        ans |= c[i]; 
        ans <<= 28;
        ans |= d[i];
        k[i] = trans(ans, pc_2, sizeof(pc_2), 56);
     }

    /* ******************** 迭代过程 ******************** */
    if (encrypt) // 加密或者解密,它们的密钥顺序是颠倒的
        for (int i = 1; i <= 16; ++i) {
            l[i] = r[i - 1];
            r[i] = (l[i - 1] ^ feistel(r[i - 1], k[i]));
        }
    else
        for (int i = 1; i <= 16; ++i) {
            l[i] = r[i - 1];
            r[i] = (l[i - 1] ^ feistel(r[i - 1], k[17 - i]));
        }

    /* ******************** 逆向置换 ******************** */
    const static char rev[64] = {
        40, 8, 48, 16, 56, 24, 64, 32,
        39, 7, 47, 15, 55, 23, 63, 31,
        38, 6, 46, 14, 54, 22, 62, 30,
        37, 5, 45, 13, 53, 21, 61, 29,
        36, 4, 44, 12, 52, 20, 60, 28,
        35, 3, 43, 11, 51, 19, 59, 27,
        34, 2, 42, 10, 50, 18, 58, 26,
        33, 1, 41,  9, 49, 17, 57, 25
    };

    uint64_t rev_input = 0;
    rev_input |= r[16];
    rev_input <<= 32;
    rev_input |= l[16];
    uint64_t rev_output = trans(rev_input, rev, sizeof(rev), 64);
    return rev_output;
}

/* 导出函数表 */
extern "C" __declspec(dllexport) inline
uint64_t des_encrypt(uint64_t m, uint64_t k) {
    return des(m, k, true);
}
extern "C" __declspec(dllexport) inline
uint64_t des_decrypt(uint64_t m, uint64_t k) {
    return des(m, k, false);
}

int _main() {
    /* 测试 */
    using namespace std;
    cout << "请输入要加密的数据(整数):";
    uint64_t plain; cin >> plain;
    cout << "请输入密钥(整数):";
    uint64_t key; cin >> key;

    uint64_t encrypted;
    cout << "加密结果,密文:" << (encrypted = des_encrypt(plain, key)) << endl;
    cout << endl;

    cout << "反向验证解密过程..." << endl << endl;
    cout << "密文:" << encrypted << ":" << endl;
    cout << "使用密钥 " << key << " 解密..." << endl;
    uint64_t decrypted;
    cout << "解密结果,明文:" << (decrypted = des_decrypt(encrypted, key)) << endl << endl;

    cout << (plain == decrypted ? 
        "加解密前后结果一致,DES 算法验证成功!" 
        : "加解密前后结果不一致,DES 算法验证失败!"
    ) << endl;


    //des_encrypt(0x0123456789ABCDEFULL, 0x133457799BBCDFF1ULL); // == 0x85E813540F0AB405ULL
    //des_decrypt(0x85E813540F0AB405ULL, 0x133457799BBCDFF1ULL); // == 0x0123456789ABCDEFULL

    return 0;
}

RSA 加密/解密算法实现

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/fusion/include/pair.hpp>
#include <boost/iostreams/stream.hpp>
#include <boost/fusion/support/pair.hpp>

using namespace boost::random;
using namespace boost::multiprecision;
using namespace std;

//#undef _DEBUG

class RSA {
private:
    static cpp_int EulerFunc(const cpp_int& p, const cpp_int& q) {
        return (p - 1) * (q - 1);
    }

    static cpp_int CalcD(const cpp_int& e, const cpp_int& euler) {
        cpp_int y = 0;
        while ((1 + euler * y) % e != 0) {
            ++y;
        }
        cpp_int d = (1 + euler * y) / e;
#if _DEBUG
        cout << "方程解: " << "(" << d.convert_to<string>() << ", " << (-y).convert_to<string>() << ")" << endl << endl;
#endif
        return d;
    }

    struct extgcd_t {
        cpp_int x;
        cpp_int y;
        cpp_int gcd;
    };

    static extgcd_t ExtendedEuclidean(cpp_int a, cpp_int b) {
        struct extgcd_t eg;
        if (b == 0) {
            eg.x = 1;
            eg.y = 0;
            eg.gcd = 0;
            return eg;
        }
        cpp_int old_gcd = a, r = b;
        cpp_int old_x = 1, s = 0;
        cpp_int old_y = 0, t = 1;
        while (r != 0) { // 扩展欧几里得算法
            cpp_int q = old_gcd / r;
            cpp_int temp = old_gcd;
            old_gcd = r;
            r = temp - q * r;
            temp = old_x;
            old_x = s;
            s = temp - q * s;
            temp = old_y;
            old_y = t;
            t = temp - q * t;
        }
        eg.x = old_x;
        eg.y = old_y;
        eg.gcd = old_gcd;
        return eg;
    }

    static cpp_int FastPow(cpp_int n, cpp_int exp, cpp_int m) {
        cpp_int ans = 1;
        n = n % m;
        while (exp != 0) {
            if (exp & 1)
                ans = (ans * n) % m;
            exp >>= 1;
            n = (n * n) % m;
        }
        return ans;
    }

public:
    struct PublicKey {
        cpp_int n;
        cpp_int e;
        PublicKey(const cpp_int& n0, const cpp_int& e0) : n(n0), e(e0) {}
        PublicKey() = default;
    };

    struct PrivateKey {
        cpp_int n;
        cpp_int d;
        PrivateKey(const cpp_int& n0, const cpp_int& d0) : n(n0), d(d0) {}
        PrivateKey() = default;
    };

    static void GenerateKeys(PublicKey& puk, PrivateKey& prk) {
        mt11213b base_gen(clock());
        independent_bits_engine<mt11213b, 512, cpp_int> gen(base_gen);
        mt19937 gen_clk(clock());

        cpp_int p, q;
        while (true) {
            p = gen();
            if (miller_rabin_test(p, 25, gen_clk)) {
#if _DEBUG
                cout << "生成随机大素数 p: " << endl << p.convert_to<string>() << endl << endl;
#endif
                break;
            }
        }

        while (true) {
            q = gen();
            if (miller_rabin_test(q, 25, gen_clk)) {
#if _DEBUG
                cout << "生成随机大素数 q: " << endl << q.convert_to<string>() << endl << endl;
#endif
                break;
            }
        }

        cpp_int n = p * q;
#if _DEBUG
        cout << "计算 p * q = n: " << n.convert_to<string>() << endl << endl;
#endif

        cpp_int euler = EulerFunc(p, q);
#if _DEBUG
        cout << "计算欧拉函数 Φ(n) = " << euler.convert_to<string>() << endl << endl;
#endif

        cpp_int e = 65537; //17

        // solve { e * x + euler * y = 1 }
#if _DEBUG
        cout << "解方程 " << e.convert_to<string>() << " * x + " + euler.convert_to<string>() + " * y = 1" << endl << endl;
#endif
        auto d = CalcD(e, euler);
#if _DEBUG
        cout << "计算模反元素 d: " << d.convert_to<string>() << endl << endl;
#endif

        puk.n = n;
        puk.e = e;

        prk.n = n;
        prk.d = d;
#if _DEBUG
        cout << "生成公钥: " << "(" << n.convert_to<string>() << ", " << e.convert_to<string>() << ")" << endl << endl;
        cout << "生成私钥: " << "(" << n.convert_to<string>() << ", " << d.convert_to<string>() << ")" << endl << endl;
#endif
    }

    static cpp_int Encrypt(cpp_int m, PublicKey puk) {
        auto c = FastPow(m, puk.e, puk.n);
#if _DEBUG
        cout << "计算 (" << m << " ^ " << puk.e << ") mod " << puk.n << " = " << c << endl << endl;
#endif
        return c;
    }

    static cpp_int Decrypt(cpp_int c, PrivateKey prk) {
        auto m = FastPow(c, prk.d, prk.n);
#if _DEBUG
        cout << "计算 (" << c << " ^ " << prk.d << ") mod " << prk.n << " = " << m << endl << endl;
#endif
        return m;
    }
};


//int main() {
//    auto eg = RSA::ExtendedEuclidean(17, 3120);
//    cout << eg.gcd << " " << eg.x << " " << eg.y << endl;
//
//    return 0;
//}



int main() {
    RSA::PublicKey puk;
    RSA::PrivateKey prk;
    RSA::GenerateKeys(puk, prk);

    cout << "请输入要加密的数据(整数):";
    cpp_int m0;
    cin >> m0; cout << endl;

    cpp_int c = RSA::Encrypt(m0, puk);
    cout << "公钥加密结果,密文:" << c << endl << endl;

    cout << "反向验证解密过程..." << endl << endl;
    cout << "密文:" << c << ":" << endl << endl;
    cout << "使用私钥解密..." << endl << endl;

    cpp_int m1 = RSA::Decrypt(c, prk);
    cout << "解密结果,明文:" << m1 << endl << endl;

    cout << (m0 == m1 ?
        "加解密前后结果一致,RSA 算法验证成功!"
        : "加解密前后结果不一致,RSA 算法验证失败!"
        ) << endl;

    return 0;
}

留下一条评论

暂无评论