문제

공개 키만 있는 경우 RSA 메시지를 어떻게 해독할 수 있나요?

예를 들어, 메시지 :21556870,12228498공개 키: (e = 15852553, n = 44331583)

나는 다음과 같은 공식이 존재한다는 것을 알고 있습니다.

gcd(e, φ(n)) = 1
ed mod φ(n) = 1

그래서 내 생각은 첫 번째 공식에 e 값을 넣은 다음 개인 키의 일부인 d를 파생시킬 수 있다는 것이었습니다.하지만 수학적으로 찾는 것은 불가능하다고 생각합니다. φ(n) 여기.그렇다면 공개 키만으로 RSA 메시지를 어떻게 해독할 수 있습니까?

도움이 되었습니까?

해결책

"공개 키만 있으면 어떻게 RSA 메시지를 해독할 수 있나요?"

잘, 공개 키에서 개인 키를 찾아야 합니다..RSA 알고리즘은 오랜 시간 동안 현장 테스트를 거친 보안 알고리즘이고 사람들은 일반적으로 충분히 긴 비트로 조심스럽게 사용하고 있기 때문에 일반적인 실제 상황에서는 수행하기가 너무 어렵습니다.

그러나 귀하에게 할당된 연습은 RSA 알고리즘을 연습할 수 있도록 설계되었습니다.사용된 숫자는 공개 키가 제공된 개인 키를 얻는 것을 방지할 만큼 크지 않습니다. 좋아하는 프로그래밍 언어와 컴퓨터를 사용하여 간단한 프로그래밍으로 모든 계산을 수행할 수 있어야 합니다.

아래 답변을 보기 전에 더 열심히 노력해 보세요.

공개 키: (e = 15852553, n = 44331583)

우리가 고려하자 n.다음은 간단한 Python 프로그램입니다.

def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

달리기 factor(44331583), 우리는 그것을 얻습니다 44331583 = 5003 * 8861.

그래서 φ(n) = (5003 - 1) * (8861 - 1) = 44317720

의 역함수 찾기 e 모듈로 φ(n).다음은 간단한 Python 프로그램입니다.

def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

달리기 inverse(15852553, 44317720), 우리는 그것을 얻습니다 15852553 * 1951097 = 1 (mod 44317720).즉, e 모듈로 φ(n) ~이다 d=1951097.

따라서 해당 개인 키는 다음과 같습니다. (d = 1951097, n = 44331583).

컴퓨팅 m**d (mod n) RSA 메시지(a.k.a.)를 해독합니다.암호문) m.다음은 널리 사용되는 모듈러 지수 함수입니다.

def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

달리기 modulo_pow(21556870, 1951097, 44331583) 그리고 modulo_pow(71, 15852553, 44331583), 우리는 각각,

21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

따라서 해독된 메시지는 다음과 같습니다. 71,111.무슨 뜻인지 알 수 있나요?

다른 팁

암호를 해독하려면 RSA 공개 키의 기반을 고려해야 합니다.이것이 요점입니다.RSA 크래킹은 인수분해와 동일하며 인수분해는 (아마도) 매우 어렵습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top