mRSA.h

#ifndef mRSA_H
#define mRSA_H

#include <stdint.h>

#define PRIME 1
#define COMPOSITE 0
#define MINIMUM_N 0x8000000000000000

#define MAX 0xFFFFFFFFFFFFFFFF

void mRSA_generate_key(uint64_t *e, uint64_t *d, uint64_t *n);
int mRSA_cipher(uint64_t *m, uint64_t k, uint64_t n);

#endif

従来定義されていたMINIMUM_N に加えてMAX を追加定義した。 MAX はuint64_t でも持てる最大の値として定義してくれた。

mRSA_generate_key

void mRSA_generate_key(uint64_t *e, uint64_t *d, uint64_t *n)
{
    uint64_t p=0, q=0;

    // miller_rabin 알고리즘을 이용하여 랜덤한 소수 p를 찾는다.
    while(1) {
        arc4random_buf(&p, sizeof(uint32_t));
				// 랜덤으로 생성된 p가 짝수라면 홀수로 만들어줌.
				if (p & 0)
            p |= 1;
        if (miller_rabin(p))
            break;
    }

    // miller_rabin 알고리즘을 이용하여 랜덤한 소수 q를 찾는다.
    while(1) {
        q = arc4random_uniform(MAX / p - MINIMUM_N/p) + MINIMUM_N/p;
				// 랜덤으로 생성된 q가 짝수라면 홀수로 만들어줌.
        if (q & 0)
            q |= 1;
        if (miller_rabin(q)) {
            if (p != q) {
                *n = p * q;
                break;
            }
            // 다시 q를 초기화하여 찾는다
            continue;
        }
    }

    // lambda 값 계산
    uint64_t lambda = ((p-1)*(q-1)) / gcd(p-1,q-1);

    // 랜덤한 암호화 키 e를 찾는다.
    // e값이 lambda보다 작으면서 gcd(e, lambda)값이 1이면 e값을 결정한다.
    while(!(*e < lambda) || !(gcd(*e, lambda) == 1))
        arc4random_buf(e, sizeof(uint64_t));
        
    // e값과 역수 관계인 d값을 찾는다.
    *d = mul_inv(*e, lambda);
}

二つの素数のp, qをまず探さなければならない。 ですから、まず、素数であるp を探して固定し、q 値をp の範囲に合わせる。

qを探すためにbufではなくuniformを利用してより早く探すために範囲を特定するようにした。 そして、ミラーラビンアルゴリズムを通過したら、p と q を掛けてn 値を計算し、もしp と q が同じではないか検査する。 そのように最終的に通過すると、breakしてwhile文を抜け、そうでなければまた別のqをrandomに探す過程を繰り返すことになる。

そのように条件を満たすランダムな2素数p,q を見つけると、lambda 値を求めた後、ランダムなe 値を探す。 lambda値より小さいながらgcd(e, lambda)が1人条件二つを同時に満足するeを繰り返し文を通じて探すことになる。

そして最終的にe値の逆数であるd値をmul_inv関数を通じて探す。

素数p, qに対する私の考え

最初はarc4random_bufを通じてp、qをつかもうとした。 まずpを探してバンボクムンを通じてqを探しているんですが、MINIMUM_Nよりnが小さければ、qを再び0にリセットして引き出せるようにした。 そうしたらrandom testでの時間がすごく長く出ており、pをarc4random_bufを通じて見つけたならば、条件に合った残りのqをどのように早く見つけるかについての悩みをしてuint64_tの範囲を利用しようと思った。

それでuint64_tの最大範囲である0x8000000000000000ですでに定められたpの大きさだけ交わしたことからMINIMUM_Nで既に定められたpの大きさだけ分けたことを除いた後にarc4random_uniformをしてくれれば、pの影響を受け、定められた範囲内でrandomが生成なるので私が前にした方式よりは、必要ない演算が減るのは事実だ。 しかし、あんなにrandomを生成すると、0から生成となるので、MINIMUM_N/pをした値を与えれば正確な範囲内でrandomナンバーが生成がなる。