首页
社区
课程
招聘
[分享]最简单的RSA实现
发表于: 2012-1-19 21:43 7301

[分享]最简单的RSA实现

2012-1-19 21:43
7301
不多说了,直接看代码吧
#define _WIN32_WINNT 0x0400
#include <windows.h>
#include <wincrypt.h>

#include <openssl/rc4.h>
#include <openssl/md5.h>
#include <openssl/sha.h>
#include <openssl/bn.h>
#include <openssl/x509v3.h>
#include <openssl/hmac.h>

#include "./bigd.h"
#include "./bigdigits.h"
/*
 * thanks to http://www.di-mgt.com.au/bigdigits.html
 */

/*
假設Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰:
隨意選擇兩個大的質數p和q,p不等於q,計算N=pq。
根據歐拉函數,不大於N且與N互質的整數個數為(p-1)(q-1)
選擇一個整數e與(p-1)(q-1)互質,並且e小於(p-1)(q-1)
用以下這個公式計算d:(d * e) mod ((p-1)(q-1)) ≡ 1
將p和q的記錄銷毀。
(N,e)是公鑰,(N,d)是私鑰。(N,d)是秘密的。Alice將她的公鑰(N,e)傳給Bob,而將她的私鑰(N,d)藏起來

http://msdn.microsoft.com/en-us/library/windows/desktop/aa382021(v=vs.85).aspx#pubkBLOBs

  PUBLICKEYSTRUC  publickeystruc;
  RSAPUBKEY rsapubkey;
  BYTE modulus[rsapubkey.bitlen/8];
  BYTE prime1[rsapubkey.bitlen/16];
  BYTE prime2[rsapubkey.bitlen/16];
  BYTE exponent1[rsapubkey.bitlen/16];
  BYTE exponent2[rsapubkey.bitlen/16];
  BYTE coefficient[rsapubkey.bitlen/16];
  BYTE privateExponent[rsapubkey.bitlen/8];

BYTE *p = pbData+ sizeof(PUBLICKEYSTRUC); 
(*(RSAPUBKEY*)p).bitlen; // 公私钥模长(以bit为单位)
(*(RSAPUBKEY*)p).pubexp; // 公钥的e(注意字节顺序)
p += sizeof(RSAPUBKEY); // 公私钥的n(注意字节顺序)
p += ((*(RSAPUBKEY*)p).bitlen)/8; // 私钥的p(注意字节顺序)
p += ((*(RSAPUBKEY*)p).bitlen)/16; // 私钥的q(注意字节顺序)
p += ((*(RSAPUBKEY*)p).bitlen)/16; // 私钥的dp(注意字节顺序)
p += ((*(RSAPUBKEY*)p).bitlen)/16; // 私钥的dq(注意字节顺序)
p += ((*(RSAPUBKEY*)p).bitlen)/16; // 私钥的qu(注意字节顺序)
p += ((*(RSAPUBKEY*)p).bitlen)/16; // 私钥的d(注意字节顺序)
*/
/*
static BYTE private_key_block[] = {
0x07,0x02,0x00,0x00,0x00,0xa4,0x00,0x00,
0x52,0x53,0x41,0x32,0x00,0x02,0x00,0x00, //RSA2 512bit <-> 64Bytes
0x01,0x00,0x01,0x00,0xcf,0x7b,0x33,0x55, //e = 0x1001 -> N
0x2b,0xc5,0x52,0xeb,0x43,0xc7,0x1c,0x7a, 
0x42,0x26,0x03,0x55,0x48,0x02,0x4b,0x7d,
0x12,0xad,0xf2,0x48,0xfa,0xb0,0x83,0xd3,
0x06,0x15,0x1d,0x7b,0xb7,0xa0,0x9a,0x53,
0x43,0x35,0x5c,0x05,0x37,0x80,0x5b,0xe3,
0xcd,0xb3,0x33,0x32,0x2e,0x49,0x19,0x4b,
0x78,0x6e,0x91,0x57,0x9b,0xe3,0xb8,0x4c, 
0x32,0xad,0xa3,0xd1,0x9b,0xac,0x8b,0x37, //p
0x46,0x39,0x01,0x47,0x06,0x70,0x6a,0x5f,
0x2c,0x77,0x9d,0xd9,0x14,0xf6,0x44,0x91,
0x37,0x15,0xb2,0x8f,0xad,0xeb,0x0e,0xf6,
0x7b,0x69,0x7c,0xfc,0xdd,0x0e,0xfd,0x8b, //q
0x66,0x21,0xea,0xf1,0x41,0xaa,0x5e,0x05,
0x78,0x77,0x64,0xf0,0x12,0x32,0x82,0x05,
0xb7,0x6f,0xd7,0x70,0x41,0xef,0x01,0xaa,
0xf5,0x9a,0x8e,0xd4,0x3b,0xc5,0x40,0x6b, //dp
0x9a,0x64,0x35,0xd9,0xbb,0xb9,0xbd,0x65, 
0x41,0xf8,0x42,0x5d,0xcc,0x6c,0x11,0x34,
0x3e,0xe6,0x09,0xf8,0x12,0xe9,0xfa,0xbf,
0x09,0x6b,0x7d,0x05,0x1d,0x9e,0x81,0xaa, //dq
0x9a,0xc0,0xb7,0xe2,0xe1,0xfc,0x8d,0x56,
0x00,0x78,0x32,0x4b,0x9b,0x74,0x0d,0x39,
0x2e,0xdf,0xe7,0x9a,0x6e,0x8b,0xa5,0xa5, 
0xfa,0xb0,0x93,0xb5,0x6a,0xfe,0xe8,0x52, //qu
0x65,0x34,0x85,0xc7,0xdf,0xbc,0x48,0xb1,
0x63,0xa1,0xf7,0xd6,0x60,0xb4,0xe7,0x51, 
0xa1,0x61,0xc4,0xb7,0x00,0x24,0xe7,0xd6,
0x84,0x90,0x0f,0xae,0x59,0xc4,0xae,0xb1, //d
0xcf,0x7a,0xee,0xeb,0x3f,0x45,0x84,0x54,
0xe3,0xfe,0x2d,0xe4,0x53,0x86,0xed,0xcb,
0x8a,0x40,0x33,0xf1,0x8c,0xb7,0x4e,0x9b,
0x72,0xe8,0x1e,0x48,0x02,0x4e,0x06,0xbc,
0xb4,0xa7,0x95,0xcc,0xd8,0xd9,0xe8,0xfa,
0x08,0xfa,0x55,0x11,0xa7,0xbf,0xaf,0x93,
0xda,0x42,0xcf,0x6a,0x03,0xae,0x85,0xd0,
0xde,0x3c,0x5b,0x91
};
*/

struct _rsa_pub_key {
        PUBLICKEYSTRUC head;
        RSAPUBKEY key_info;
};

#define SEC_MAX_MODULUS_SIZE    256
#define SEC_EXPONENT_SIZE       4

static void
reverse(unsigned char * p, int len)
{
        int i, j;
        unsigned char temp;

        for (i = 0, j = len - 1; i < j; i++, j--)
        {
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
        }
}

#if _DEBUG

void
ssl_rsa_encrypt(unsigned char * out, unsigned char * in, int len, unsigned int modulus_size, unsigned char * modulus,
                unsigned char * exponent)
{
        BN_CTX *ctx;
        BIGNUM mod, exp, x, y;
        unsigned char inr[SEC_MAX_MODULUS_SIZE];
        int outlen;
        
        reverse(modulus, modulus_size);
        reverse(exponent, SEC_EXPONENT_SIZE);
        memcpy(inr, in, len);
        reverse(inr, len);
        
        ctx = BN_CTX_new();
        BN_init(&mod);
        BN_init(&exp);
        BN_init(&x);
        BN_init(&y);
        
        BN_bin2bn(modulus, modulus_size, &mod);
        BN_bin2bn(exponent, SEC_EXPONENT_SIZE, &exp);
        BN_bin2bn(inr, len, &x);
        BN_mod_exp(&y, &x, &exp, &mod, ctx);
        outlen = BN_bn2bin(&y, out);
        reverse(out, outlen);
        if (outlen < (int) modulus_size)
                memset(out + outlen, 0, modulus_size - outlen);
        
        BN_free(&y);
        BN_clear_free(&x);
        BN_free(&exp);
        BN_free(&mod);
        BN_CTX_free(ctx);
}
#endif

static void dump_hex(unsigned char* data, int len)
{
        int i;
        for (i=0; i<len; i++) {
                printf("0x%02x,", data[i]);
                if ((i % 8) == 7)
                        printf("\n");
        }
}

static DWORD make_rsa_keys(unsigned char* key_blocks, DWORD key_len)
{
        HCRYPTPROV hProv;
        HCRYPTKEY hKey = NULL;
        DWORD dwResult, dwBlobLen;

        dwResult = -1;

        if (!CryptAcquireContext(&hProv, NULL, MS_ENHANCED_PROV, PROV_RSA_FULL, 0)){
                dwResult = GetLastError();
                if (dwResult == NTE_BAD_KEYSET) {
                        if (!CryptAcquireContext(&hProv, NULL, MS_DEF_PROV, PROV_RSA_FULL, CRYPT_NEWKEYSET)) {
                                dwResult = GetLastError();
                                goto err_exit;
                        }
                }
        }

        /*
        if (!CryptImportKey(hProv, private_key_block, sizeof(private_key_block),
                0, 0, &hKey)){
                dwResult = GetLastError();
                return dwResult;
        }
        */

        /* Create a EXCHANGE key pair */
        if (!CryptGenKey(hProv, AT_KEYEXCHANGE, CRYPT_EXPORTABLE, &hKey)){
                dwResult = GetLastError();
                goto err_exit;
        }

        /* 返回密钥数据长度 */
        if (!CryptExportKey(hKey, NULL, PRIVATEKEYBLOB, 0, NULL, &dwBlobLen)) {
                dwResult = GetLastError();
                goto err_exit;
        }
        
        if (key_len < dwBlobLen)
                goto err_exit;

        if (!CryptExportKey(hKey, NULL, PRIVATEKEYBLOB, 0, key_blocks, &dwBlobLen)) {
                dwResult = GetLastError();
                return dwResult;
        }
        
        printf("RSA-keys:\n");
        dump_hex(key_blocks, dwBlobLen);
        printf("\n");
        return dwBlobLen;

err_exit:

        if (hKey)
                CryptDestroyKey(hKey);

        if (hProv)
                CryptReleaseContext(hProv, 0);

        return -1;
}

int main(int argc, char** argv)
{
        BYTE rsa_keys[1024] = {0};
        struct _rsa_pub_key* pub_key = rsa_keys;

        BYTE in_data[256] = {0};
        BYTE out[256] = {0};
        
        BYTE tmp_N[256] = {0};
        BYTE tmp_e[4] = {0};

        BYTE *p = rsa_keys + sizeof(PUBLICKEYSTRUC);
        int bitlen;

        BIGD N = bdNew();
        BIGD d = bdNew();
        BIGD e = bdNew();
        BIGD c = bdNew(); //密文
        BIGD m = bdNew(); //明文

        /* 产生一个RSA密钥对 */
        make_rsa_keys(rsa_keys, sizeof(rsa_keys));

        printf("RSA %dbits e=%d\n", pub_key->key_info.bitlen, pub_key->key_info.pubexp);
        bitlen = pub_key->key_info.bitlen;

        p += sizeof(RSAPUBKEY); // 公私钥的n(注意字节顺序)        
        p += (bitlen)/8; // 私钥的p(注意字节顺序)
        p += (bitlen)/16; // 私钥的q(注意字节顺序)
        p += (bitlen)/16; // 私钥的dp(注意字节顺序)
        p += (bitlen)/16; // 私钥的dq(注意字节顺序)
        p += (bitlen)/16; // 私钥的qu(注意字节顺序)
        p += (bitlen)/16; // 私钥的d(注意字节顺序)

        //bdConvFromOctets(d, p, bitlen/8);
        //bdPrintHex("d=0x", d, "\n");

        memcpy(tmp_N, rsa_keys+sizeof(struct _rsa_pub_key), bitlen/8);
        memcpy(tmp_e, &pub_key->key_info.pubexp, 4);

        bdConvFromOctets(N, tmp_N, bitlen/8);
        bdPrintHex("N=0x", N, "\n");

        bdConvFromOctets(e, tmp_e, 4);
        bdPrintHex("e=0x", e, "\n");

        strcpy(in_data, "0123456789");
        bdConvFromOctets(m, in_data, bitlen/8);

        /* RSA加密 */
        bdModExp(c, m, e, N);
        bdPrintHex("c=0x", c, "\n");

        bdFree(&c);
        bdFree(&m);
        bdFree(&e);
        bdFree(&N);
        bdFree(&d);

#if _DEBUG
        ssl_rsa_encrypt(out, in_data, 64, 
                pub_key->key_info.bitlen/8, 
                rsa_keys+sizeof(struct _rsa_pub_key),
                &pub_key->key_info.pubexp
                );
#endif

        return 0;
}

RSA_test.rar

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

上传的附件:
收藏
免费 0
支持
分享
最新回复 (4)
雪    币: 100
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
这个算法看代码都累 要是逆向的话那还不得死人了
2012-1-19 22:29
0
雪    币: 247
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
能不能用私钥加密 公钥解密呢???
2012-1-20 10:25
0
雪    币: 603
活跃值: (40)
能力值: ( LV9,RANK:140 )
在线值:
发帖
回帖
粉丝
4
。。。。。。。
2012-1-21 09:31
0
雪    币: 773
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
你说的这是签名的情况
2012-5-22 09:39
0
游客
登录 | 注册 方可回帖
返回
//