대형 키로 RSA 암호 해독

내 문제 : RSA 시스템의 개인 키와 공개 키를 이미 알고 있으며 암호화 된 메시지가 있지만 개인 비공개 지수가 약 1024 비트이기 때문에 암호를 해독 할 수 없습니다. 내 데이터는 세부 사항에 필요하다면 따라야하지만 질문은 간단한 가정용 PC에서 긴 키가있는 메시지를 해독하는 방법입니다. c이 암호문이다대형 키로 RSA 암호 해독

N = 0xb197d3afe713816582ee988b276f635800f728f118f5125de1c7c1e57f2738351de8ac643c118a5480f867b6d8756021911818e470952bd0a5262ed86b4fc4c2b7962cd197a8bd8d8ae3f821ad712a42285db67c85983581c4c39f80dbb21bf700dbd2ae9709f7e307769b5c0e624b661441c1ddb62ef1fe7684bbe61d8a19e7 
e = 65537 
p = 0xc315d99cf91a018dafba850237935b2d981e82b02d994f94db0a1ae40d1fc7ab9799286ac68d620f1102ef515b348807060e6caec5320e3dceb25a0b98356399 
q = 0xe90bbb3d4f51311f0b7669abd04e4cc48687ad0e168e7183a9de3ff9fd2d2a3a50303a5109457bd45f0abe1c5750edfaff1ad87c13eed45e1b4bd2366b49d97f 
d = 0x496747c7dceae300e22d5c3fa7fd1242bda36af8bc280f7f5e630271a92cbcbeb7ae04132a00d5fc379274cbce8c353faa891b40d087d7a4559e829e513c97467345adca3aa66550a68889cf930ecdfde706445b3f110c0cb4a81ca66f8630ed003feea59a51dc1d18a7f6301f2817cb53b1fb58b2a5ad163e9f1f9fe463b901 
c = 0x58ae101736022f486216e290d39e839e7d02a124f725865ed1b5eea7144a4c40828bd4d14dcea967561477a516ce338f293ca86efc72a272c332c5468ef43ed5d8062152aae9484a50051d71943cf4c3249d8c4b2f6c39680cc75e58125359edd2544e89f54d2e5cbed06bb3ed61e5ca7643ebb7fa04638aa0a0f23955e5b5d9

, N는 e 및 d은 공공 및 민간 지수이며, 모듈 각각과 p 및 q 소수가 (난 그렇게 생각하지만, 확인하기 어렵다)입니다.

나는 이미 this 및 몇 가지 다른 온라인 서비스를 사용하려고했습니다. 또한 내 컴퓨터에서 python rsa library을 사용했지만 오류가 발생하여 실패합니다.

m = c**d % N

또는

이

m = 1 
for i in xrange(d): 
    m = (m * c) % N

이

그래서 어쩌면보기의 수학 지점에서 더 영리한 방법이 m이 계산된다 나는 다음과 같은 공식이 모든 곳에서 사용 (일반 텍스트에 대한 m 스탠드를 가정)라고 가정 더 빨리, 또는 그것을 해결할 수있는 온라인 서비스, 또는 도서관. 또는 수퍼 컴퓨터가 1024 비트 지수 RSA 해독을 계산할 수 있습니까?

데이터는 CTF 컨텍스트 picoctf에서 가져옵니다.

출처

2014-10-31 user2872765

우선이 정보는 중요하지 않으며 (b)이 키 쌍을 다시 사용할 필요가 없습니다. 이제이 암호문과 다른 암호화 된 메시지를 해독 할 수 있기 때문입니다. 그것으로 당신에게 보냈습니다.

우리는 다음과 같은 (a 헥스 인코딩 문자열 결과) 파이썬 메시지를 디코딩 할 수

가

m = hex(pow(c, d, N)).rstrip("L")

부이을

0x436f6e67726174756c6174696f6e73206f6e2064656372797074696e6720616e20525341206d6573736167652120596f757220666c6167206973206d6f64756c61725f61726974686d65746963735f6e6f745f736f5f6261645f61667465725f616c6c

을주는 ltin pow 함수는 exponentiation by squaring을 사용하여 정수를 모듈화하여 큰 힘을 효율적으로 계산합니다. 제곱과 그 변형에 의한 지수화가 없다면 이산 로그 (Discrete Logarithm) 문제에 의존하는 비대칭 키 알고리즘의 사용이 불가능합니다. 사실 구현하기가 쉽기 때문에 그렇게하는 것이 좋습니다. 자세한 내용은 위키 백과 문서를 참조하십시오.

출처

2014-10-31 19:10:03 sju

슈퍼! 그것이 내가 검색 한 것과 정확히 같습니다. 그리고이 수학 트릭에 대해 전에는 들어 보지 못했습니다. 매우 유용합니다. 필자가 작성한 것처럼 데이터는 상황에 따라 다르므로 사용하지 않을 것이며 정보는 게임에만 해당됩니다. – user2872765

대형 키로 RSA 암호 해독

답변

관련 문제