πŸ” RSA μ•Œκ³ λ¦¬μ¦˜

문제

κ³΅κ°œν‚€ μ•Œκ³ λ¦¬μ¦˜ 쀑 Rivest, Shamir, Adleman에 μ˜ν•΄ μ„€κ³„λœ RSA μ•Œκ³ λ¦¬μ¦˜μ„ κ΅¬ν˜„ν•˜λΌ

둜직

  1. 2개의 μ†Œμˆ˜ (p, q)κ°€ ν•„μš”ν•˜λ‹€
  2. n = p * q
  3. Ο•(n) = (p-1) * (q-1)
  4. e = e와 Ο•(n)의 μ„œλ‘œμ†Œ
  5. d = e*d mod Ο•(n) = 1
  6. c = m^e mod n
  7. m = c^d mod n

주의 사항

  1. μ•”ν˜Έν™”ν•˜λŠ” 평문은 n의 μžλ¦Ώμˆ˜λ³΄λ‹€ μž‘μ€ 자릿수λ₯Ό κ°€μ Έμ•Όν•œλ‹€. a. 평문이 '123456789'이고, n이 '1234'이면 평문을 '123', '456', 789'둜 λ‚˜λˆ μ„œ μ•”ν˜Έν™”ν•΄μ•Όν•œλ‹€.
  2. p와 qλŠ” λ‹€μŒ 쑰건을 λ§Œμ‘±ν•΄μ•Ό ν•œλ‹€. a. p와 qλŠ” 같지 μ•Šκ³  거의 같은 크기의 μžλ¦Ώμˆ˜μ•Όμ•Ό ν•œλ‹€. b. p-1κ³Ό q-1은 μ»€λ‹€λž€ μ†ŒμΈμˆ˜λ₯Ό 각각 κ°€μ Έμ•Ό ν•œλ‹€. c. p-1κ³Ό q-1의 μ΅œλŒ€ κ³΅μ•½μˆ˜λŠ” μž‘μ€ μˆ˜μ—¬μ•Ό ν•œλ‹€

κ΅¬ν˜„ν•˜μ§€ μ•Šμ•˜μ§€λ§Œ, TMI

  1. μ‹€μ œ RSAμ—μ„œ μ‚¬μš©ν•˜λŠ” p와 qλŠ” 100자리 μ •λ„μ˜ μ†Œμˆ˜λ‘œ 거의 같은 크기의 자릿수λ₯Ό κ°€μ§€λŠ” 수λ₯Ό μ„ νƒν•œλ‹€.

μ½”λ“œ

rsa.h

#ifndef _RSA
#define _RSA

typedef struct key
{
    long pkey;  // 초기 2개의 μ†Œμˆ˜ p와 qκ°€ κ³±ν•΄μ„œ λ‚˜μ˜€λŠ” n이 μ €μž₯될 λ³€μˆ˜
    long ekey;  // public-key
    long dkey;  // private-key
    int pkey_size;

} Key;

class Rsa
{
public:
    Rsa();
    virtual ~Rsa();

public:
    Key produce_keys();
    long endecrypt(const long msg, const long key, const long pkey);
    int sizeof_int(long data);

private:
    long produce_pkey(const long prime1, const long prime2);
    long produce_ekey(const long orla);
    long produce_dkey(const long ekey, const long orla);
    long produce_prime();
    long produce_orla(const long prime1, const long prime2);
    long produce_gcd(const long a, const long b);
    bool is_prime(const long digit);
};

#endif

main.cpp

#include "rsa.h"
#include <iostream>

using namespace std;

int main(void)
{
    Rsa rsa;
    Key key = rsa.produce_keys();
    cout << "=============================" << endl;
    cout << "=========== R S A ===========" << endl;
    cout << "=============================\n" << endl;

    cout << "=====================================" << endl;
    cout << "μ•”ν˜Έν™” ν›„ 얻은 ν‚€λŠ” λ‹€μŒκ³Ό κ°™μŠ΅λ‹ˆλ‹€."<< endl;
    cout << "n ν‚€ : " << key.pkey << endl;
    cout << "μ•”ν˜Έν™” ν‚€ (κ³΅κ°œν‚€) : " << key.ekey << endl;
    cout << "μ•”ν˜Έ 해독 ν‚€ (κ°œμΈν‚€) : " << key.dkey << endl;
    cout << "=====================================\n" << endl;
    long msg;
    cout << "μ•”ν˜Έν™”ν•  정보λ₯Ό μž…λ ₯ν•˜μ‹­μ‹œμ˜€ (숫자, λ„ˆλ¬΄ 클 수 μ—†μŒ) : ";
    cin >> msg;
    cout << "\n=====================================" << endl;
    long msg_des = rsa.endecrypt(msg, key.ekey, key.pkey);
    cout << "μ•”ν˜Έν™”λœ μ •λ³΄λŠ” λ‹€μŒκ³Ό κ°™μŠ΅λ‹ˆλ‹€ : " << msg_des << endl;
    msg_des = rsa.endecrypt(msg_des, key.dkey, key.pkey);
    cout << "μ•”ν˜Έ ν•΄λ…λœ λ©”μ‹œμ§€λŠ” λ‹€μŒκ³Ό κ°™μŠ΅λ‹ˆλ‹€ : " << msg_des << endl;
    cout << "=====================================" << endl;
    return 0;
}

rsa.cpp

#include "rsa.h"
#include <cstdlib>
#include <ctime>
#include <string>
#include <bitset>
#include <iostream>

using namespace std;

Rsa::Rsa()
{
}

Rsa::~Rsa()
{
}
/***********************************************************************
μ•”ν˜Έν™” λ³΅ν˜Έν™”λ₯Ό λ™μ‹œμ— μ§„ν–‰ν•˜λŠ” λ©”μ†Œλ“œ
c = m^e mod n
m = c^d mod n
λΌλŠ” 식은 κ°™κ³  λ³€μˆ˜λ§Œ λ§€κ°œκ°’λ§Œ λ°”λ€Œλ©΄ λ˜λ―€λ‘œ ν•˜λ‚˜μ˜ λ©”μ†Œλ“œμ—μ„œ μ²˜λ¦¬ν•¨
***********************************************************************/
long Rsa::endecrypt(const long msg, const long key, const long pkey)
{
    long msg_des = 1;
    long root = msg;
    long index = key;
    //int n_size = sizeof_int(pkey);
    //int msg_size = sizeof_int(msg);
    //int size = msg_size / n_size;
    //if (msg_size % n_size)
    //  size = size + 1;

    while (index)
    {
        //cout << bitset<32>(index) << endl;
        if (index & 1) {
            msg_des = (msg_des * root) % pkey;
            //cout << "msg_des : " << msg_des << endl;
        }
        index >>= 1;
        //cout << "b root : " << root << endl;
        root = (root * root) % pkey;
        //cout << "a root : " << root << endl;
    }
    return msg_des;
}


/************************************
 p와 qλ₯Ό μƒμ„±ν•΄μ„œ
 n, e, d ν‚€λ₯Ό 생성
 * *********************************/
Key Rsa::produce_keys()
{
    long prime1 = produce_prime();  // p
    long prime2 = produce_prime();  // q
    while (prime2 == prime1)        // p와 qλŠ” n을 λ§Œλ“€κ³  폐기해야 ν•˜κΈ° λ•Œλ¬Έμ—
        prime2 = produce_prime();   // λ”°λ‘œ μ €μž₯ν•΄μ„œ λ©”μ†Œλ“œ λ°–μœΌλ‘œ 빼지 μ•ŠμŒ

    Key key;
    long orla = produce_orla(prime1, prime2);   // 였일러 n 생성
    key.pkey = produce_pkey(prime1, prime2);    // n 생성
    key.ekey = produce_ekey(orla);              // e 생성
    key.dkey = produce_dkey(key.ekey, orla);    // d 생성
    return key;
}

/************************************
 N ν‚€ 생성
 p * q
 * *********************************/
long Rsa::produce_pkey(const long prime1, const long prime2)
{
    return prime1 * prime2;
}

/************************************
 였일러 n 생성
************************************/
long Rsa::produce_orla(const long prime1, const long prime2)
{
    return (prime1 - 1) * (prime2 - 1);
}

/************************************
 μ•”ν˜Έν™” ν‚€ (κ³΅κ°œν‚€) e 생성
 * *********************************/
long Rsa::produce_ekey(const long orla)
{
    long ekey;
    while (true)
    {
        ekey = rand() % orla;   // 랜덀 수λ₯Ό 였일러 n으둜 λ‚˜λ¨Έμ§€ μ—°μ‚°
        if (ekey >= 2 && produce_gcd(ekey, orla) == 1)  // e-key와 였일러 n이 μ„œλ‘œμ†ŒμΈμ§€ νŒλ³„
            break;
    }
    return ekey;
}

/************************************
 λ³΅ν˜Έν™” ν‚€ (κ°œμΈν‚€) d 생성
 * *********************************/
long Rsa::produce_dkey(const long ekey, const long orla)
{
    long dkey = orla / ekey;
    while (true)
    {
        if (((dkey * ekey) % orla) == 1)
            break;
        else 
            ++dkey;
    }
    return dkey;
}

/************************************
 [100, 200] λ²”μœ„μ—μ„œ μž„μ˜μ˜ μ†Œμˆ˜ 생성
 * *********************************/
long Rsa::produce_prime()
{
    long prime = 0;
    srand(time(0));
    while (true)
    {
        prime = rand() % 100 + 100;
        if (is_prime(prime))
            break;
    }
    return prime;
}

/************************************
 두 숫자의 μ΅œλŒ€ κ³΅μ•½μˆ˜ 생성        
 * *********************************/
long Rsa::produce_gcd(const long a, const long b)
{
    long dividend = a;
    long divisor = b;
    long residual = dividend % divisor;
    while (residual)
    {
        dividend = divisor;
        divisor = residual;
        residual = dividend % divisor;
    }
    return divisor;
}

/************************************
 μ†Œμˆ˜μΈμ§€ νŒλ‹¨
 * *********************************/
bool Rsa::is_prime(const long digit)
{
    int tmp = 2;
    while (tmp < digit)
        if (!(digit % tmp++))
            break;

    if (tmp == digit)
        return true;
    return false;
}

/************************************
 μž…λ ₯κ°’μ˜ 자릿수 νŒλ‹¨
 * *********************************/
int Rsa::sizeof_int(long data)
{
    int pos = 1;
    
    if (data < 0)
        data *= (-1);

    for (int i = 0; ; i++, pos++) {
        if ((data /= 10) <= 0)
            break;
    }

    return pos;
}

κ²°κ³Ό

μ°Έκ³ λ¬Έν—Œ

GitHub, "RSA Encryption Decryption", https://github.com/cassvin/Rsa, (2020.06.05.)

이 글이 도움이 λ˜μ—ˆλ‚˜μš”?
0 minutes ago
μž‘μ„±λœ λŒ“κΈ€μ΄ μ—†μŠ΅λ‹ˆλ‹€. 첫 λŒ“κΈ€μ„ λ‹¬μ•„λ³΄μ„Έμš”!
    λŒ“κΈ€μ„ μž‘μ„±ν•˜λ €λ©΄ 둜그인이 ν•„μš”ν•©λ‹ˆλ‹€.