암호 해독가로서 항상 나를 놀라게하는 한 가지 : 소수를 사용하는 것이 왜 그렇게 중요한가? 암호화에서 왜 그렇게 특별합니까?
누구든지 간단한 간단한 설명이 있습니까? (나는 많은 입문서가 있고 Applied Cryptography가 성경이라는 것을 알고 있지만 말 그대로 : 나는 내 자신의 암호화 알고리즘을 구현하려고하지 않고 발견 된 것들이 뇌를 폭발하게 만들었습니다-10 페이지의 수학 공식 없음 제발 :))
모든 답변에 감사드립니다 . 나는 실제 개념을 가장 명확하게 한 것을 받아 들였다.
답변
가장 기본적이고 일반적인 설명 : 암호화는 모두 숫자 이론 에 관한 것이며 모든 정수 (0과 1 제외)는 소수로 구성되므로 소수 이론에서 소수를 다루는 것입니다.
보다 구체적으로, RSA 와 같은 일부 중요한 암호화 알고리즘 은 많은 수의 소인수 분해 에 오랜 시간이 걸린다는 사실에 크게 좌우됩니다 . 기본적으로 메시지를 암호화하는 데 사용되는 두 개의 큰 소수로 구성된 “공개 키”와 메시지를 해독하는 데 사용되는 두 개의 소수로 구성된 “비밀 키”가 있습니다. 공개 키를 공개로 만들 수 있으며 모든 사람이 공개 키를 사용하여 메시지를 암호화 할 수 있지만 주요 요소를 알고 메시지를 해독 할 수 있습니다. 다른 모든 사람들은 수 이론의 현재 상태를 감안할 때 실용적 이기에는 너무 오래 걸리는 숫자를 고려해야합니다.
답변
단순한? 예.
두 개의 큰 소수를 곱하면 두 개의 큰 소수만있는 큰 비 프라임 숫자를 얻게됩니다.
그 수를 고려하면 사소한 작업이 아니며, 그 사실은 많은 암호화 알고리즘의 원천입니다. 자세한 내용은 단방향 기능 을 참조하십시오.
부록 : 조금만 더 설명하겠습니다. 두 소수의 곱은 공개 키로 사용할 수 있지만 소수는 개인 키로 사용할 수 있습니다. 두 가지 요소 중 하나를 알면 실행 취소 할 수있는 데이터에 대한 모든 작업은 암호화하기에 쉽지 않습니다.
답변
다음은 매우 간단하고 일반적인 예입니다.
RSA 암호화 알고리즘 일반적으로 안전한 상거래 웹 사이트에 사용되는, 반대를 할 매우 어려운 반면,이 (매우 큰) 소수와 다중 데리고 쉽다는 사실을 기반으로 – 의미 : 테이크 a를 두 개의 주요 요소 만 가지고있는 것을 감안할 때 매우 큰 숫자입니다.
답변
중요한 소수 자체는 아니지만 소수와 함께 작동하는 알고리즘입니다. 특히, 숫자 (모든 숫자)의 요인을 찾는 중입니다.
아시다시피, 숫자에는 적어도 두 가지 요소가 있습니다. 소수는 정확히 두 가지 요소 인 1과 그 자체가 있다는 점에서 고유 한 속성을 갖습니다.
인수 분해가 중요한 이유는 수학자와 컴퓨터 과학자가 가능한 모든 조합을 시도하지 않고 숫자를 인수 분해하는 방법을 모르기 때문입니다. 즉, 먼저 2, 3, 4 등으로 나눕니다. 소수, 특히 매우 큰 소수를 고려하려고하면 2와 그 큰 소수 사이의 가능한 모든 숫자를 (본질적으로) 시도해야합니다. 가장 빠른 컴퓨터에서도 암호화에 사용되는 소수의 숫자를 고려하는 데 몇 년 (수백 년)이 걸릴 것입니다.
우리는 암호화 알고리즘에 강도를 부여하는 많은 수를 효율적으로 인수 분해하는 방법을 모른다는 사실입니다. 언젠가 누군가가 방법을 알아 내면 현재 사용하는 모든 암호화 알고리즘이 더 이상 사용되지 않습니다. 이것은 열린 연구 영역으로 남아 있습니다.
답변
정수를 주요 요소로 분해하는 빠른 알고리즘을 아는 사람이 없기 때문입니다. 그러나 소수 요인이 특정 정수로 곱해 지는지 확인하는 것은 매우 쉽습니다.
답변
암호화에 대한 좋은 자료가 있습니다. 여기 하나가 있습니다 :
해당 페이지에서 :
1977 년 Ron Rivest, Adi Shamir 및 Len Adleman이 발명 한 가장 일반적으로 사용되는 공개 키 암호화 시스템에서 공개 키와 개인 키는 비교적 간단한 수학 공식에 따라 한 쌍의 큰 소수에서 파생됩니다. 이론적으로 수식을 거꾸로 사용하여 공개 키에서 개인 키를 파생시킬 수 있습니다. 그러나 소수의 제품 만 공개되고, 그 크기의 숫자를 소수로 고려하면 세계에서 가장 강력한 슈퍼 컴퓨터조차도 일반 공개 키를 깰 수 없습니다.
Bruce Schneier의 책 Applied Cryptography 도 있습니다. 나는 그 책을 강력히 추천한다. 재미 있어요.
답변
RSA가 소수의 속성을 사용하는 방법에 대해 좀 더 구체적으로 설명하기 위해 RSA 알고리즘은 Euler ‘Theorem 에 결정적으로 의존합니다. Euler의 정리 는 비교적 소수 인 “a”와 “N”의 경우 a ^ e는 1 modulo N에 합치합니다 . e는 오일러의 N 의 끈기있는 함수 입니다.
프라임은 어디에서 발생합니까? 오일러의 N의 유능함 함수를 효율적으로 계산하려면 N의 소인수 분해를 알아야합니다. RSA 알고리즘의 경우, 일부 소수 (p) 및 “q”에 대해 N = pq 인 경우 e = (p-1) (q -1) = N-p-q + 1. 그러나 p와 q를 모르면 e의 계산은 매우 어렵습니다.
더 추상적으로, 많은 crypotgraphic 프로토콜 은 계산하기 쉽지만 반전하기 어려운 다양한 trapdoor 함수 를 사용합니다. 숫자 이론은 이러한 트랩 도어 함수의 풍부한 소스 (예 : 큰 소수의 곱셈)이며 소수는 절대적으로 숫자 이론의 중심입니다.