은행 금고를 보호해야 하는 시나리오를 생각해 보세요. 작업 첫날에 제공되는 열쇠 없이는 절대 난공불락으로 간주됩니다. 귀하의 목표는 키를 안전하게 저장하는 것입니다.

필요에 따라 스토리지에 대한 액세스를 제공하면서 항상 키를 보관하기로 결정했다고 가정해 보겠습니다. 그러나 스토리지를 열 때마다 물리적인 존재가 필요하기 때문에 그러한 솔루션이 실제로는 잘 확장되지 않는다는 것을 빨리 깨닫게 될 것입니다. 약속했던 휴가는 어떻게 되나요? 게다가 질문은 훨씬 더 무섭습니다. 유일한 열쇠를 잃어버리면 어떻게 될까요?

휴가를 염두에 두고 열쇠의 복사본을 만들어 다른 직원에게 맡기기로 결정했습니다. 그러나 이것이 이상적이지 않다는 것도 이해합니다. 열쇠 개수를 두 배로 늘리면 열쇠 도난 확률도 두 배로 늘어납니다.

필사적으로, 당신은 복제본을 파괴하고 원래 키를 반으로 나누기로 결정했습니다. 이제 키 조각을 가지고 있는 신뢰할 수 있는 두 사람이 키를 수집하고 저장소를 열려면 물리적으로 존재해야 한다고 생각할 수 있습니다. 이는 도둑이 두 개의 조각을 훔쳐야 한다는 것을 의미하는데, 이는 하나의 열쇠를 훔치는 것보다 두 배나 어렵습니다. 그러나 누군가가 키의 절반을 잃어버리면 전체 키를 복구할 수 없기 때문에 이 방식이 키 하나보다 낫지 않다는 것을 곧 알게 됩니다.

일련의 추가 키와 잠금 장치를 사용하여 문제를 해결할 수 있지만 이 접근 방식을 사용하려면 신속하게 много 열쇠와 자물쇠. 보안이 전적으로 한 사람에게만 의존하지 않도록 키를 공유하는 것이 이상적인 디자인이라고 결정했습니다. 또한 하나의 조각이 손실된 경우(또는 사람이 휴가를 가는 경우) 전체 키가 계속 작동하도록 조각 수에 대한 임계값이 있어야 한다는 결론을 내립니다.

비밀을 공유하는 방법

이러한 유형의 키 관리 체계는 Adi Shamir가 1979년 자신의 작품을 출판할 때 생각한 것입니다. "비밀을 공유하는 방법". 이 기사에서는 소위 말하는 것을 간략하게 설명합니다. 비밀 값(예: 암호화 키)을 효율적으로 분할하기 위한 임계값 체계 부속. 그렇다면, 언제, 그리고 적어도 언제만 으로 부품을 조립하면 비밀을 쉽게 복원할 수 있습니다. .

보안 관점에서 볼 때 이 체계의 중요한 속성은 공격자가 최소한 부속. 존재감마저도 부품은 어떠한 정보도 제공해서는 안 됩니다. 우리는 이것을 부동산이라고 부른다. 의미론적 보안.

다항식 보간

샤미르 임계값 체계 컨셉으로 제작되었습니다 다항식 보간. 이 개념에 익숙하지 않다면 실제로는 매우 간단합니다. 사실, 그래프에 점을 그린 다음 이를 선이나 곡선으로 연결해 본 적이 있다면 이미 사용한 것입니다!

두 점을 통해 2차 다항식을 무제한으로 그릴 수 있습니다. 그중 하나만 선택하려면 세 번째 점이 필요합니다. 삽화: 위키 백과

XNUMX차 다항식을 고려하면, . 이 함수를 그래프에 표시하려면 몇 개의 점이 필요합니까? 글쎄, 우리는 이것이 선을 형성하는 선형 함수이므로 최소한 두 개의 점이 필요하다는 것을 알고 있습니다. 다음으로, XNUMX차 다항식 함수를 고려해보세요. . 이는 XNUMX차 함수이므로 그래프를 그리려면 최소 XNUMX개의 점이 필요합니다. XNUMX차 다항식은 어떻습니까? 최소 XNUMX점. 등등.

이 속성의 정말 멋진 점은 다항식 함수의 차수와 최소한 점, 우리는 이 다항식 함수에 대한 추가 점을 도출할 수 있습니다. 우리는 이러한 추가 점의 외삽을 호출합니다. 다항식 보간.

비밀 만들기

여기에서 Shamir의 영리한 계획이 작용한다는 것을 이미 깨달으셨을 것입니다. 우리의 비밀을 말해보자 -가요 . 우리는 돌릴 수 있다 그래프의 한 지점으로 그리고 차수를 갖는 다항식 함수를 생각해 보세요. , 이는 이 점을 만족시킨다. 이를 상기시켜 드리겠습니다. 이는 필요한 조각의 임계값이므로 임계값을 조각 XNUMX개로 설정하면 XNUMX차 다항식 함수를 선택해야 합니다.

우리의 다항식은 다음과 같은 형식을 갖습니다. 어디에서 и — 무작위로 선택된 양의 정수. 우리는 차수를 갖는 다항식을 구성하고 있습니다. , 여기서 자유 계수는  - 이게 우리의 비밀이에요 , 그리고 이후의 각 항목에 대해 용어에는 무작위로 선택된 양의 계수가 있습니다. 원래의 예로 돌아가서 다음과 같이 가정하면 , 그러면 우리는 함수를 얻습니다 .

이 시점에서 연결을 통해 조각을 생성할 수 있습니다. 의 고유한 정수 어디에서 (이건 우리의 비밀이니까) 이 예에서는 임계값이 XNUMX인 XNUMX개의 조각을 배포하려고 하므로 무작위로 포인트를 생성합니다. 그리고 키의 관리자인 XNUMX명의 신뢰할 수 있는 사람에게 각각 한 포인트를 보냅니다. 우리는 또한 사람들에게 그 사실을 알립니다. , 이는 공개 정보로 간주되어 복구에 필요하기 때문입니다. .

비밀을 되찾는 중

우리는 이미 다항식 보간의 개념과 이것이 Shamir의 임계값 체계의 기초가 되는 방법에 대해 논의했습니다. . XNUMX명의 수탁자 중 XNUMX명이 복원을 원할 때 , 보간만 하면 됩니다. 자신만의 독특한 포인트로 이를 위해 그들은 자신의 포인트를 결정할 수 있습니다 다음 공식을 사용하여 라그랑주 보간 다항식을 계산합니다. 프로그래밍이 수학보다 더 명확하다면 pi는 본질적으로 연산자입니다. for, 이는 모든 결과를 곱하고 시그마는 for, 모든 것을 합산합니다.

에 우리는 이것을 이렇게 풀 수 있고 원래의 다항식 함수를 반환할 수 있습니다:

우리는 그것을 알고 있기 때문에 , 회복 간단하게 완료되었습니다:

안전하지 않은 정수 산술 사용

Shamir의 기본 아이디어를 성공적으로 적용했지만 , 지금까지 무시했던 문제가 남아 있습니다. 우리의 다항식 함수는 안전하지 않은 정수 산술을 사용합니다. 공격자가 함수 그래프에서 추가 포인트를 얻을 때마다 다른 포인트에 대한 가능성이 줄어듭니다. 정수 산술을 사용하여 다항식 함수에 대해 증가하는 점 수를 플롯하면 이를 직접 눈으로 볼 수 있습니다. 이는 우리가 명시한 보안 목표에 역효과를 낳습니다. 왜냐하면 공격자는 최소한 파편.

정수 산술 회로가 얼마나 약한지 보여주기 위해 공격자가 두 점을 획득한 시나리오를 생각해 보십시오. 그리고 다음과 같은 공개 정보를 알고 있습니다. . 이 정보로부터 그는 추론할 수 있다 , XNUMX와 같고 알려진 값을 공식에 ​​대입합니다. и .

그러면 공격자는 다음을 찾을 수 있습니다. , 계산 :

우리가 정의했기 때문에 무작위로 선택된 양의 정수이므로 가능한 개수가 제한되어 있습니다. . 공격자는 이 정보를 사용하여 추론할 수 있습니다. , 5보다 큰 것은 무엇이든 가능하기 때문에 부정적인. 우리가 결정했기 때문에 이것은 사실로 밝혀졌습니다.

그러면 공격자는 가능한 값을 계산할 수 있습니다. 교체 в :

제한된 옵션으로 값을 선택하고 확인하는 것이 얼마나 쉬운지 분명해집니다. . 여기에는 다섯 가지 옵션만 있습니다.

안전하지 않은 정수 연산 문제 해결

이 취약점을 제거하기 위해 Shamir는 모듈러 연산을 사용하여 다음을 대체할 것을 제안합니다. 에 어디에서 и — 모든 소수의 집합.

모듈러 연산이 어떻게 작동하는지 빨리 기억해 봅시다. 바늘이 달린 시계는 친숙한 개념입니다. 그녀는 다음과 같은 시계를 사용합니다. . 시침이 12시를 지나면 다시 XNUMX시로 돌아갑니다. 이 시스템의 흥미로운 특성은 단순히 시계만 보면 시침이 몇 번이나 회전했는지 추론할 수 없다는 것입니다. 그러나 시침이 XNUMX를 네 번이나 지나갔다는 것을 알면 간단한 공식을 사용하여 경과한 시간을 완전히 알 수 있습니다. 어디에서  우리의 제수입니다 (여기서 ),  계수(제수가 나머지 없이 원래 숫자에 들어가는 횟수, 여기서는 ),  나머지는 일반적으로 모듈로 연산자 호출을 반환합니다(여기서는 ). 이 모든 값을 알면 방정식을 풀 수 있습니다. , 그러나 계수를 놓치면 결코 원래 값을 복원할 수 없습니다.

이전 예제에 체계를 적용하고 다음을 사용하여 이것이 우리 체계의 보안을 어떻게 향상시키는지 보여줄 수 있습니다. . 새로운 다항식 함수 , 그리고 새로운 포인트 . 이제 키 키퍼는 다항식 보간법을 다시 사용하여 함수를 재구성할 수 있습니다. 이번에는 덧셈과 곱셈 연산에 모듈로 감소가 수반되어야 합니다. (예 : ).

이 새로운 예를 사용하여 공격자가 이러한 새로운 점 중 두 가지를 배웠다고 가정해 보겠습니다. 및 공개 정보 . 이번에 공격자는 자신이 가지고 있는 모든 정보를 바탕으로 다음과 같은 함수를 출력합니다.  는 모든 양의 정수의 집합이고, 모듈러스 계수를 나타냅니다. .

이제 공격자가 다시 찾아냅니다. , 계산 :

그런 다음 그는 다시 시도합니다. 교체 в :

이번에 그에게 심각한 문제가 생겼습니다. 수식 누락값 , и . 이러한 변수의 조합은 무한하므로 추가 정보를 얻을 수 없습니다.

보안 고려 사항

Shamir의 비밀 공유 계획은 다음과 같습니다. 정보 이론의 관점에서 본 보안. 이는 수학이 무제한의 컴퓨팅 능력을 가진 공격자에게도 저항할 수 있음을 의미합니다. 그러나 회로에는 여전히 몇 가지 알려진 문제가 포함되어 있습니다.

예를 들어 Shamir의 계획은 다음을 생성하지 않습니다. 확인할 조각즉, 사람들은 가짜 조각을 자유롭게 제시하고 올바른 비밀을 복구하는 것을 방해할 수 있습니다. 충분한 정보를 가진 적대적인 조각 보관자는 변경을 통해 또 다른 조각을 생성할 수도 있습니다. 귀하의 재량에 따라. 이 문제는 다음을 사용하여 해결됩니다. 검증 가능한 비밀 공유 계획, Feldman의 계획과 같은.

또 다른 문제는 모든 조각의 길이가 해당 비밀의 길이와 동일하므로 비밀의 길이를 쉽게 결정할 수 있다는 것입니다. 이 문제는 사소한 것으로 해결될 수 있다 심 최대 고정 길이의 임의 숫자로 구성된 비밀입니다.

마지막으로, 우리의 보안 문제는 설계 자체 이상으로 확장될 수 있다는 점에 유의하는 것이 중요합니다. 실제 암호화 애플리케이션의 경우 공격자가 애플리케이션 실행 시간, 캐싱, 충돌 등에서 유용한 정보를 추출하려고 시도하는 부채널 공격의 위협이 있는 경우가 많습니다. 이것이 우려되는 경우 개발 중에 함수 및 상수 조회와 같은 보호 조치 사용, 메모리가 디스크에 저장되지 않도록 방지 및 이 기사의 범위를 벗어나는 기타 여러 가지 고려 사항을 신중하게 고려해야 합니다.

Демо

에 이 페이지 Shamir의 비밀 공유 계획에 대한 대화형 데모가 있습니다. 도서관을 기반으로 한 시연 ssss-js, 그 자체는 인기 있는 프로그램의 JavaScript 포트입니다. ssss는. 큰 값을 계산하는 데 유의하세요. , и 시간이 걸릴 수 있습니다.

출처 : habr.com