제가 알기로는 정확하게는 해싱하는걸로 알고 있습니다.
MD5도 해싱알고리즘으로 알고 있는데 아닌가요??
주변에 도서관이나 서점서 해싱에 관련된 책이나
데이터 구조, 알고리즘 이런 책들 보시면 아마 나와있을겁니다.
사실 암호화라 하면 정확히는 암호를 풀 수 있어야 암호화라 할 수 있지요.
다시는 풀 수 없게 만들고 암호화라 하면 좀 이상한 듯 합니다.
암호라는 단어 자체가 그런뜻이 아닌가 하는 제 생각입니다.
그래서 일단은 해싱이 맞는 듯 하구요.
랜덤한 시드값을 가지고 일정한 데이터를 해싱하기 때문에
그 결과만 가지고는 거꾸로 풀 수 가 없습니다. 다만 같은 알고리즘으로
여러가지 데이터를 해싱해서 찾고자하는 것과 일치한 결과를 얻을때까지
돌려 보면 되겠죠. 대부분의 사전 공격 툴이 이렇게 공격합니다.
그래서 사전에 있는 단어 같은걸 패스워드에 쓰지 말라는 거죠.
Hash자체에 대해서는 제가 설명하기는 너무 지식이 부족하고 책이나
인터넷을 뒤져보시면 왜 역함수가 존재할 수 없는지 쉽게 아시게 될겁니다.
전 암호화 관련 프로그램을 해보진 않았지만
수학을 배울 시절에 잠시 접할 기회가 있었습니다.
위에서 많은 분들이 잘 말씀해 주셨지만
암호화의 종류가 여러개가 있습니다.
그 목적이 다른데요
1. 복호화가 필요한 암호화 2. 복호화가 안되는 암호화
이렇게 나눌 수 있습니다. 보통 암호화라 한다면 1번의 이야기를 하죠
1번은 간단히 말해서 역함수가 없는 것이 아닙니다.
예를 들어보죠//실제로 이런 알고리즘이 쓰입니다 RSA의 경우...//
A = P1 * P2 라고 생각해보면 (P1과 P2는 매우큰 소수)
우리는 A라는 수에서 P1과 P2를 생각해 내기는 어렵지만
반대로 위 의 연산에서 A라는 수를 얻어내는 건 쉽습니다.
결국 1번의 암호화라는 것은 정당한 키가 없으면 복호화가 어려운
함수를 쓰는 것입니다. 역연산이 시간이 많이 걸리게 되죠
하지만 정당한 키 P1이 있다면 P2를 구하는 것은 무지 쉽습니다.
보통 DES에는 이를 응용한 지수모듈러 연산을 씁니다.
즉 1번은 암호를 풀 수 있습니다.
다만 시간이 무지 걸릴뿐이죠 컴퓨터 속력이 빨라지면서 이런 암호의 복호화
속도가 빨라지므로 저 P1과 P2길이를 늘리는 거죠 요새는 128비트키를
많이 씁니다. 특히 DES는 32비트를 쓰다가 하두 컴터가 좋아져서
역연산이 빨리 이루어지므로 3번 연속으로 암호화하는 3DES를 쓰빈다.
그런데 이 연산이 정방향으로 이루어지는 경우에도 로드가 걸리는게 많고
그에 반해 얻는 것이 쉽게 풀리므로 요새는 린델?? 알고리즘 - AES라고 불립니다.
- Advanced encryption system?? 을 씁니다.
아무튼 이런 암호는 전부 이론적으로 복호화가 가능합니다.
하지만 2번의 이야기는 다름니다.
2번은 원래 Hash 함수가 빠른 검색을 위해 미리 정한 규칙에 의해
키값을 만드는 것을 이용합니다. 그래서 어떤 스트링이 정한 규칙에 따라
키가 만들어 지면 그것이 바로 암호화가 되었다고 생각합니다.
그러나 이 키로 원래의 스트링을 복원하진 못합니다.
위에 분 말씀대로 얼마의 정보는 빼고 특수한 -MD5같은- 알고리즘을 써서
키값을 만들기 떄문입니다.
이 경우 역시 정방향의 속도는 빨라야 합니다.
다만 몇가지 문제가 있습니다.
string_a => 해쉬후 key_c
string_b => 해쉬후 key_c
즉 해쉬는 그 특성상 다른 입력값을 넣어도 같은 키값이 나올 수 있습니다.
즉 암호가 틀려도 맞게 될 상황이 있을 수 있습니다. - 전적으로 이론적입니다.
그리하여 암호시스켐에 쓰이는 것은
보통 강한 충돌 회피성을 갖는 다고 알려져 있습니다.
이 말은 즉슨 입력이 틀리면 아웃풋도 거의 틀리더라... 라는 걸 보장하빈다.
강하다는 말이 애매모호하지만 적어도 3des로 풀릴정도의 시도로는 안풀린다의 의미정도 아닐까요?
크 본론으로 돌아와서 그럼 이제 리눅스의 암호시스틈은 무얼 써야하는지
명백합니다. 관리자가 전혀 사용자들의 암호를 알 필요가 없기떄문에
당연히!!!!! 2번의 암호시스템을 써야합니다.
1번의 경우는 서로간의 암호화된 메시지 전달 -VPN virtual private network정도?- 이 필요로 할떄 쓰입니다.
저는 암호학에도 흥미가 많아서 //정확히 이야기하면 다니는 회사가 -_-...
하지만 전 코더는 아닙니다. 물론 수학자도 아니죠 ^^//
C/C++로 구현하는 암호학 이라는 책을 보고 있습니다.
한번 보세요
RSA라는 공개키 기반과 위의 AES시스템에도 나와있습니다.
RSA는 정말 흥미롭습니다. ^^
PS : 지금 옆에 책도 없고 오랜만의 기억을 떠올리는 거라
많이 틀렸을 것입니다. 오류 지적 부탁드립니다.
일반적으로 리눅스나 유닉스에서 사용되는 패스워드의 해쉬 알고리즘을 통과한 후의 공간의 크기를 보면 대충 납득이 될지도 모르겠네요.
128bit의 길이, 즉 16바이트니까 총 2^128의 가지의 경우가 있다고 생각됩니다.
아무리 사람들이 사용할 수 있는 패스워드의 공간의 크기가 크다고 해도 2^128승의 공간을 생각하면 별로 크지 않다고 볼 수 있으니 다른 두개의 password를 hashing한 결과가 collision이 발생할 확률은 무지 적겠네요. (물론 확률이 적을뿐이지 같은 결과 hash 값이 나오는 password들이 존재하긴 할 것이라고 생각합니다)
ps. 2^128의 공간은 전 우주에 존재하는 쿼크단위의 미립자의 수보다도 훨씬 많다고 하니까요.. :)
지수모듈러 연산은 RSA 등의 공개키 알고리즘에서 많이 사용합니다.
DES는 substitution, permutation, XOR 연산을 여러번 반복하는 방법으로 이루어지죠.
Quote:
그리하여 암호시스켐에 쓰이는 것은
보통 강한 충돌 회피성을 갖는 다고 알려져 있습니다.
약한 충돌 회피성이란
고정된 x에 대해 h(x)=h(x')인 x와 다른 x'을 찾기 힘든 것을 말하고
강한 충돌 회피성이란
h(x')=h(x)인 서로 다른 (x, x') 쌍을 (고정된 x가 아닌) 찾기 힘든 것을 말합니다.
약한 충돌 회피성만 가질 때 사용할 수 있는 공격방법이 존재하기 때문에 안전한 hash 함수는 강한 충돌 회피성을 만족해야 하는 것으로 알고 있습니다.
Quote:
크 본론으로 돌아와서 그럼 이제 리눅스의 암호시스틈은 무얼 써야하는지
명백합니다. 관리자가 전혀 사용자들의 암호를 알 필요가 없기떄문에
당연히!!!!! 2번의 암호시스템을 써야합니다.
1번의 경우는 서로간의 암호화된 메시지 전달 -VPN virtual private network정도?- 이 필요로 할떄 쓰입니다.
암호학 관련 책에 보면 어떤 보안 시스템이 달성하고자 하는 목적에는
confidentiality, integrity, authentication, non-repudiation 등이 있을 수 있다고 합니다.
이들 중 어떤 것들을 만족시켜야 하는가에 따라 대칭키 알고리즘, 공개키 알고리즘 혹은 해쉬 function 중 어떤 것을 써야 할까를 결정하는 것이구요.
리눅스의 암호시스템의 경우는 authentication이 목적이기 때문에 hash function이 가장 적당하겠구요 추가로 confidentiality가 필요하게 되면 대칭키 알고리즘, non-repudiation 까지 필요하다 하면 공개키 알고리즘을 사용하는 식이 되겠죠.
원문의 링크는 아래와 같습니다. http://no-smok.net/nsmk/_be_cf_c8_a3#line41
----------------------------------------->
RSA는 현재 일반적으로 가장 많이 쓰이는 암호화알고리즘으로, 그 알고리즘은 극히 단순하다. 하지만, 이것은 수학적으로 shortcut이 없는 것으로 알려진 DLP(Dicrete Log Problem)으로서 전형적인 one way function이다. 그 과정은 다음과 같다.
1. 키 생성 : 큰 소수(prime) 두 개 p와 q를 선정하고 곱해서 n 을 만든다. exponent e를 고르고, d = (e^(-1))mod ((p-1)(q-1))의 관계를 가지는 d를 찾는다. 앞에서 즉 e*d mod n = 1이다. e = (p-1)(q-1)과 서로소이다.
2. 암호화 : C = (M^e) mod n
3. 복호화 : M = (C^d) mod n
간단하게 증명할 수도 있다. 오일러함수란 것을 알아야한다. 오일러함수 E(N) 은 N 보다 작고 N과 서로소인 자연수의 개수를 나타내며, E(AB) = E(A)E(B)인 성질을 가지고 있다. 또한, P가 소수(prime)일 경우 E(P) = P-1이다. 왜냐하면 소수보자 작은 모든 수는 소수와 서로소이기 때문이다. 이 때 오일러정리란 a와 N이 서로소일 때, a^(E(N)) mod N = 1 이다. 이때,
C^d mod n = (M^e)^d = M^ed = M^((p-1)(q-1)+1) = (M^(p-1)(q-1))*M mod n = 오일러정리에 의해 M
즉, RSA를 깨는 방법은 d를 찾는 과정이며 n으로부터 p와 q를 알아내야한다. 이것은 즉, IFP(Integer Factorization problem)으로 환원된다. 이것은 아직까지 풀지 못한다는 증명도 없지만, 효율적인 알고리즘 또한 개발되지 않았다.
y = f(x)x = g(y)f 는 존재하지만, g는 존재
y = f(x)
x = g(y)
f 는 존재하지만, g는 존재하지 않는다라는 뜻이죠. 즉, x로부터 y는 쉽게 구할 수 있지만, y 로부터 x를 쉽게(컴퓨터를 이용해도 몇억년 이상 혹은 영원히) 구할 수 없다는 것입니다.
즉, password encoding string만으로 password를 구할 수 없다는 것입니다.
단방향 함수라고도 하며, unix 전통적으로는 crypt 라는 함수를 사용합니다.
---
http://coolengineer.com
md5도 그러한 종류인데, 불안하시면 패스워드의 암호화를 md5로 바꿔주
md5도 그러한 종류인데, 불안하시면 패스워드의 암호화를 md5로 바꿔주실 수 있을 겁니다.
힘없는자의 슬픔
흠...책에 역함수가 존재하지 않는다라고 적혀 있나요?제가 알기로
흠...책에 역함수가 존재하지 않는다라고 적혀 있나요?
제가 알기로는 역함수가 존재하는 것이 증명되진 않았다라고 알고
있는데요.
수학적으로 증명되어 있다면 좋겠지만....쩝
역함수가 없다는것 말고도
암호화 하면서 자료의 일부를 의도적으로 버려서 decoding되는 것을 막는
것으로 알고 있는데 아닌가요?
단방향 암호화...
제가 알기로는 정확하게는 해싱하는걸로 알고 있습니다.
MD5도 해싱알고리즘으로 알고 있는데 아닌가요??
주변에 도서관이나 서점서 해싱에 관련된 책이나
데이터 구조, 알고리즘 이런 책들 보시면 아마 나와있을겁니다.
사실 암호화라 하면 정확히는 암호를 풀 수 있어야 암호화라 할 수 있지요.
다시는 풀 수 없게 만들고 암호화라 하면 좀 이상한 듯 합니다.
암호라는 단어 자체가 그런뜻이 아닌가 하는 제 생각입니다.
그래서 일단은 해싱이 맞는 듯 하구요.
랜덤한 시드값을 가지고 일정한 데이터를 해싱하기 때문에
그 결과만 가지고는 거꾸로 풀 수 가 없습니다. 다만 같은 알고리즘으로
여러가지 데이터를 해싱해서 찾고자하는 것과 일치한 결과를 얻을때까지
돌려 보면 되겠죠. 대부분의 사전 공격 툴이 이렇게 공격합니다.
그래서 사전에 있는 단어 같은걸 패스워드에 쓰지 말라는 거죠.
Hash자체에 대해서는 제가 설명하기는 너무 지식이 부족하고 책이나
인터넷을 뒤져보시면 왜 역함수가 존재할 수 없는지 쉽게 아시게 될겁니다.
제 짧은 지식이니 너무 믿지는 마시길...
caramis.
from caramis ~ !
살짝 붙이는 질문입니다.Hash Function의 Random S
살짝 붙이는 질문입니다.
Hash Function의 Random Seed 값은 어떻게 정해지는 것인가요? 한 시스템에서는 일정하게 유지가 되야 할 것이라는 생각이 드는데요. :)
전에 친구와 이야기하다 결론이 안났던 기억이 들어서 말이죠. :D
My Passion for the Vision!
[quote="Viz"]Hash Function의 Random Seed
Random Seed이니만큼 특별히 지정하지 않는 한 랜덤하게 결정합니다.
대신 결과 문자열에 덧붙여서 보관하지요.
(Crypt라면 맨 앞 2글자라던지 하는 식입니다)
그래서 그 문자열 자체만 가지고도 무작위 대입으로 원래 값을 알아낼 수 있지요.
음...
그럼 무결성문제는 어떻게 되나요?암호는 자료의 integrity를 보장하는 범위내
에서 이루어지는 것입니다.저작자의 의도와 달리 자료가 변질되거나 손실을 막
기위해 암호화가 이루집니다.
pynoos님이 말씀하신 것처럼 역함수가 존재한다고 하는 것은 이미 암호로써
는 이미 쓸모없는 것 아닙니까?
좋은 날 즐거운 날....
Re: 음...
이 부분은 암호화라는 단어를 어떻게 사용하냐에 대한 문제인듯 싶습니다.
본질적인 의미의 암호화는 복호화가 가능한걸 전제로 합니다. 기밀을 보존하기 위해 사용하는 것이지요.
단순히, "오소리 3단계에 뻐꾸기가 심었다." 라는 말도 암호라고 할 수 있으니까요. 물론 내용을 알 수 있는건 이 암호를 알고 있는 사람들 뿐이겠지만요.
SSL을 통한 전송을 암호화 통신이라고 하기도 하듯이... 말입니다.
한글에서 encryption과 password 및 hash를 구분하기가 모호한게 문제겠지요.
잘 모르는 초보가 한번 써봅니다. 전 암호화 관련 프로그램을 해보
잘 모르는 초보가 한번 써봅니다.
전 암호화 관련 프로그램을 해보진 않았지만
수학을 배울 시절에 잠시 접할 기회가 있었습니다.
위에서 많은 분들이 잘 말씀해 주셨지만
암호화의 종류가 여러개가 있습니다.
그 목적이 다른데요
1. 복호화가 필요한 암호화
2. 복호화가 안되는 암호화
이렇게 나눌 수 있습니다. 보통 암호화라 한다면 1번의 이야기를 하죠
1번은 간단히 말해서 역함수가 없는 것이 아닙니다.
예를 들어보죠//실제로 이런 알고리즘이 쓰입니다 RSA의 경우...//
A = P1 * P2 라고 생각해보면 (P1과 P2는 매우큰 소수)
우리는 A라는 수에서 P1과 P2를 생각해 내기는 어렵지만
반대로 위 의 연산에서 A라는 수를 얻어내는 건 쉽습니다.
결국 1번의 암호화라는 것은 정당한 키가 없으면 복호화가 어려운
함수를 쓰는 것입니다. 역연산이 시간이 많이 걸리게 되죠
하지만 정당한 키 P1이 있다면 P2를 구하는 것은 무지 쉽습니다.
보통 DES에는 이를 응용한 지수모듈러 연산을 씁니다.
즉 1번은 암호를 풀 수 있습니다.
다만 시간이 무지 걸릴뿐이죠 컴퓨터 속력이 빨라지면서 이런 암호의 복호화
속도가 빨라지므로 저 P1과 P2길이를 늘리는 거죠 요새는 128비트키를
많이 씁니다. 특히 DES는 32비트를 쓰다가 하두 컴터가 좋아져서
역연산이 빨리 이루어지므로 3번 연속으로 암호화하는 3DES를 쓰빈다.
그런데 이 연산이 정방향으로 이루어지는 경우에도 로드가 걸리는게 많고
그에 반해 얻는 것이 쉽게 풀리므로 요새는 린델?? 알고리즘 - AES라고 불립니다.
- Advanced encryption system?? 을 씁니다.
아무튼 이런 암호는 전부 이론적으로 복호화가 가능합니다.
하지만 2번의 이야기는 다름니다.
2번은 원래 Hash 함수가 빠른 검색을 위해 미리 정한 규칙에 의해
키값을 만드는 것을 이용합니다. 그래서 어떤 스트링이 정한 규칙에 따라
키가 만들어 지면 그것이 바로 암호화가 되었다고 생각합니다.
그러나
이 키로 원래의 스트링을 복원하진 못합니다.
위에 분 말씀대로 얼마의 정보는 빼고 특수한 -MD5같은- 알고리즘을 써서
키값을 만들기 떄문입니다.
이 경우 역시 정방향의 속도는 빨라야 합니다.
다만 몇가지 문제가 있습니다.
string_a => 해쉬후 key_c
string_b => 해쉬후 key_c
즉 해쉬는 그 특성상 다른 입력값을 넣어도 같은 키값이 나올 수 있습니다.
즉 암호가 틀려도 맞게 될 상황이 있을 수 있습니다. - 전적으로 이론적입니다.
그리하여 암호시스켐에 쓰이는 것은
보통 강한 충돌 회피성을 갖는 다고 알려져 있습니다.
이 말은 즉슨 입력이 틀리면 아웃풋도 거의 틀리더라... 라는 걸 보장하빈다.
강하다는 말이 애매모호하지만 적어도 3des로 풀릴정도의 시도로는 안풀린다의 의미정도 아닐까요?
크 본론으로 돌아와서 그럼 이제 리눅스의 암호시스틈은 무얼 써야하는지
명백합니다. 관리자가 전혀 사용자들의 암호를 알 필요가 없기떄문에
당연히!!!!! 2번의 암호시스템을 써야합니다.
1번의 경우는 서로간의 암호화된 메시지 전달 -VPN virtual private network정도?- 이 필요로 할떄 쓰입니다.
저는 암호학에도 흥미가 많아서 //정확히 이야기하면 다니는 회사가 -_-...
하지만 전 코더는 아닙니다. 물론 수학자도 아니죠 ^^//
C/C++로 구현하는 암호학 이라는 책을 보고 있습니다.
한번 보세요
RSA라는 공개키 기반과 위의 AES시스템에도 나와있습니다.
RSA는 정말 흥미롭습니다. ^^
PS : 지금 옆에 책도 없고 오랜만의 기억을 떠올리는 거라
많이 틀렸을 것입니다. 오류 지적 부탁드립니다.
C++, 그리고 C++....
죽어도 C++
암호화 하고 해쉬 알고리즘은 틀리지 않나요?자료의 원형이 일치하는
암호화 하고 해쉬 알고리즘은 틀리지 않나요?
자료의 원형이 일치하는지 확인하기 위해 해쉬한 결과값을 비교하기 위해
사용하는것 아니였나요?
(제가 잘 몰라서 여쭙는겁니다)
- advanced -
역함수가 존재하지 않을 가능성이 큰 함수는 이런식이되겠지요..y
역함수가 존재하지 않을 가능성이 큰 함수는 이런식이되겠지요..
y = x % 5
y의 값이 어떠한 값이 나왔는데...
그 y의 값을 이용하여 y의 값을 만들어낸 x값을 알아낼수 없죠
(x값이 무지 많으니까요..)
해쉬같은 것도 이런식으로 알고 있습니다
같은 값이 나올수있겠지요 위에서 처럼 (x=1, 6....)
해쉬들도 같은 값은 나올수 있지만 그 확률이 매우매우 적다고 알고 있습
니다
복호 가능한 암호화는 언젠간 유추할수 있지만 해쉬되어 있는 것은
거의 유추가 불가능 한걸로 알고 있습니다
MD5같은 것은 해쉬 알고리즘이니까 안전하다고 보셔도 될듯 합니다
일반적으로 리눅스나 유닉스에서 사용되는 패스워드의 해쉬 알고리즘을 통과한
일반적으로 리눅스나 유닉스에서 사용되는 패스워드의 해쉬 알고리즘을 통과한 후의 공간의 크기를 보면 대충 납득이 될지도 모르겠네요.
128bit의 길이, 즉 16바이트니까 총 2^128의 가지의 경우가 있다고 생각됩니다.
아무리 사람들이 사용할 수 있는 패스워드의 공간의 크기가 크다고 해도 2^128승의 공간을 생각하면 별로 크지 않다고 볼 수 있으니 다른 두개의 password를 hashing한 결과가 collision이 발생할 확률은 무지 적겠네요. (물론 확률이 적을뿐이지 같은 결과 hash 값이 나오는 password들이 존재하긴 할 것이라고 생각합니다)
ps. 2^128의 공간은 전 우주에 존재하는 쿼크단위의 미립자의 수보다도 훨씬 많다고 하니까요.. :)
My Passion for the Vision!
잘 설명해 주셨는데 한가지 실수하신 부분이 있군요 ^^[quote
잘 설명해 주셨는데 한가지 실수하신 부분이 있군요 ^^
지수모듈러 연산은 RSA 등의 공개키 알고리즘에서 많이 사용합니다.
DES는 substitution, permutation, XOR 연산을 여러번 반복하는 방법으로 이루어지죠.
약한 충돌 회피성이란
고정된 x에 대해 h(x)=h(x')인 x와 다른 x'을 찾기 힘든 것을 말하고
강한 충돌 회피성이란
h(x')=h(x)인 서로 다른 (x, x') 쌍을 (고정된 x가 아닌) 찾기 힘든 것을 말합니다.
약한 충돌 회피성만 가질 때 사용할 수 있는 공격방법이 존재하기 때문에 안전한 hash 함수는 강한 충돌 회피성을 만족해야 하는 것으로 알고 있습니다.
암호학 관련 책에 보면 어떤 보안 시스템이 달성하고자 하는 목적에는
confidentiality, integrity, authentication, non-repudiation 등이 있을 수 있다고 합니다.
이들 중 어떤 것들을 만족시켜야 하는가에 따라 대칭키 알고리즘, 공개키 알고리즘 혹은 해쉬 function 중 어떤 것을 써야 할까를 결정하는 것이구요.
리눅스의 암호시스템의 경우는 authentication이 목적이기 때문에 hash function이 가장 적당하겠구요 추가로 confidentiality가 필요하게 되면 대칭키 알고리즘, non-repudiation 까지 필요하다 하면 공개키 알고리즘을 사용하는 식이 되겠죠.
참고로..
전에 제가 올렸던 쓰레든데, no-smok에서 관련 부분을 찾은 것 같아 올려봅니다.
원문의 링크는 아래와 같습니다.
http://no-smok.net/nsmk/_be_cf_c8_a3#line41
----------------------------------------->
RSA는 현재 일반적으로 가장 많이 쓰이는 암호화알고리즘으로, 그 알고리즘은 극히 단순하다. 하지만, 이것은 수학적으로 shortcut이 없는 것으로 알려진 DLP(Dicrete Log Problem)으로서 전형적인 one way function이다. 그 과정은 다음과 같다.
1. 키 생성 : 큰 소수(prime) 두 개 p와 q를 선정하고 곱해서 n 을 만든다. exponent e를 고르고, d = (e^(-1))mod ((p-1)(q-1))의 관계를 가지는 d를 찾는다. 앞에서 즉 e*d mod n = 1이다. e = (p-1)(q-1)과 서로소이다.
2. 암호화 : C = (M^e) mod n
3. 복호화 : M = (C^d) mod n
간단하게 증명할 수도 있다. 오일러함수란 것을 알아야한다. 오일러함수 E(N) 은 N 보다 작고 N과 서로소인 자연수의 개수를 나타내며, E(AB) = E(A)E(B)인 성질을 가지고 있다. 또한, P가 소수(prime)일 경우 E(P) = P-1이다. 왜냐하면 소수보자 작은 모든 수는 소수와 서로소이기 때문이다. 이 때 오일러정리란 a와 N이 서로소일 때, a^(E(N)) mod N = 1 이다. 이때,
C^d mod n = (M^e)^d = M^ed = M^((p-1)(q-1)+1) = (M^(p-1)(q-1))*M mod n = 오일러정리에 의해 M
즉, RSA를 깨는 방법은 d를 찾는 과정이며 n으로부터 p와 q를 알아내야한다. 이것은 즉, IFP(Integer Factorization problem)으로 환원된다. 이것은 아직까지 풀지 못한다는 증명도 없지만, 효율적인 알고리즘 또한 개발되지 않았다.
--->
데비안 & 우분투로 대동단결!
댓글 달기