SRVB 암호화 시스템 시작하기

게시 됨: 2022-03-11

소개

정보 보안은 이론적인 컴퓨터 과학에서 소프트웨어 엔지니어링에 이르기까지 모든 것을 포함할 수 있는 매혹적인 지식 분야이며 인간 오류의 심리학을 관찰할 수도 있습니다.

암호화는 이제 우리 일상 생활의 많은 익명의 기술 영웅 중 하나입니다. 민감한 정보를 다루는 소셜 네트워크, 웹 뱅킹, 군사 정보 및 기타 정보 시스템은 모두 암호화에 크게 의존합니다. 암호화를 통해 우리는 개인 정보를 보호할 수 있습니다. 일부에서는 이를 12번째 인권으로 간주합니다.

이 기사에서는 공개 키 암호 시스템의 원리를 소개하고 기사 작성자와 Daniel Santana Rocha 교수가 개발한 암호 시스템인 Santana Rocha-Villas Boas(SRVB)를 소개합니다. 이 글을 쓰는 시점에서 알고리즘 작성자는 코드를 해독하는 데 성공한 사람에게 금전적 보상이 포함된 캠페인을 준비하고 있습니다. 이 기사에서는 알고리즘 기능을 자세히 다루므로 여기에서 상금을 노리는 것이 가장 좋습니다. 더 자세한 정보는 SRVB 사이트에서 확인할 수 있습니다.

암호 시스템이란 무엇입니까?

암호화는 일반적으로 소위 "키"라고 하는 특정 명령이 제공되는 한 메시지를 해석할 수 있는 방법을 허용하면서 메시지의 해석 가능성을 방해하는 모든 방법입니다. 이것은 가장 초기의 기술까지 포괄하는 매우 광범위한 정의이지만 정보 보안에 대한 모든 것을 다루지는 않는다는 점을 언급할 가치가 있습니다.

암호화 방법과 이를 해독하는 방법 간의 기술 경쟁에서 최종 승자는 없을 것으로 예상됩니다. 각각의 새로운 세대는 암호화된 메시지를 체계적으로 해독/해독하는, 즉 보안 또는 암호화를 우회하는 일련의 기술인 정보 보안 및 암호 분석의 표준을 높일 것으로 예상됩니다.

암호 시스템(주어진 암호화 기술)이 사용자에게 안전한 것으로 간주되기 위해서는 국제 전문가 커뮤니티의 승인을 받아야 하며 따라서 Kerckhoffs의 원칙으로 알려진 공개적으로 알려져야 합니다. 그러나 바로 이 조건으로 인해 시스템이 암호화를 체계적으로 깨는 방법을 고안하려고 시도할 세계 암호 분석 커뮤니티의 정밀 조사에 노출됩니다.

주어진 암호화 프로세스를 의도된 에이전트만 암호를 해독할 수 있을 정도로 비밀로 하는 동시에 세계의 암호 분석 커뮤니티가 그 견고함을 증명할 수 있을 정도로 공개하려면 어떻게 해야 합니까? 답은 암호학의 핵심 요소인 키(key)에 있습니다. 암호 시스템의 키는 암호화 또는 암호 해독 알고리즘 또는 둘 다에 대한 매개변수입니다. 알고리즘 패밀리가 아닌 매개변수를 비밀로 유지함으로써 상충되는 두 가지 요구 사항을 모두 달성할 수 있습니다. 매개변수 패밀리가 충분히 크고(무한할 수도 있음) 해당 구성 요소 각각이 적절한 속성을 가지고 있음이 입증될 수 있다면 공격자가 단순히 검사를 통해 매개변수를 결정하는 것은 불가능합니다.

마지막으로, 키가 효과적으로 작동하려면 쉽게 생성되어야 하지만 추측하는 것은 거의 불가능해야 합니다. 오늘날 컴퓨터의 계산 능력으로 인해 컴퓨터는 인간이 생성한 키를 해독하는 데 인간이 상상할 수 있는 것보다 더 적은 시간이 필요하며, 어쨌든 그런 방식으로 키를 생성하는 것은 비용 효율적이지 않다는 사실에 더하여 말입니다. 그 때문에 키는 알고리즘에 의해 생성되는 경향이 있습니다.

키 생성 알고리즘은 일반적인 사용의 결과로 예측 가능/재현 가능한 출력을 생성해서는 안 됩니다. 알고리즘은 지능적인 프로세스 없이 절차를 수행하므로 이것이 어떻게 수행될 수 있는지가 문제입니다. 답은 키 생성 알고리즘을 많은 양의 진정한 무작위 비트를 키로 변환하는 맵으로 바꾸는 것입니다. 진정한 무작위 비트는 우주의 불확실성에서 생성하는 운영 체제에서 얻을 수 있습니다. 일부 소스는 응용 프로그램에 따라 마우스 움직임, 네트워크 패키지 지연 또는 전용 하드웨어일 수 있습니다.

공개 키 암호 시스템

이제 우리가 방금 말한 것과 모순되는 것처럼 보이는 개념인 공개 키를 소개할 것이기 때문에 다시 한 번 놀랄 준비를 하십시오.

지금까지 비밀 매개변수(키)가 안전하게 교환된 후 보안 통신이 생성되는 것을 보았지만 공개 채널을 통해 매개변수를 교환하는 문제는 여전히 남아 있습니다. 바로 지금, 우리는 조금 더 명백한 문제인 보안 채널 생성을 해결하는 개념을 소개할 것입니다.

Alice가 Bob과 함께 작업하고 있고 그들이 암호화를 사용하여 작업 상호 작용을 안전하게 유지하기를 원한다고 가정합니다. 그들은 서로에게 키가 있는 USB 플래시 드라이브를 제공하여 암호화 키를 만나고 교환할 수 있습니다. 그러나 Alice와 Bob이 다른 대륙에 있다면 어떨까요? 존재하지 않는 보안 채널을 설정하는 방법은 무엇입니까?

경쟁자인 Eve가 교환을 가로채서 나중에 모든 암호화된 데이터를 읽는 데 키를 사용할 수 있기 때문에 이메일을 통해 키를 보내는 것은 옵션이 아닙니다. 그들이 이 민감한 데이터를 전송할 수 있는 다른 디지털 채널이 있다면 애초에 암호화와 키가 필요하지 않을 것입니다. 물리적 메일을 통해 키를 보내는 것 역시 가로챌 수 있습니다. 처음에는 민감한 정보를 교환해야 하기 때문입니다. 다른 데이터 안에 숨어서 스테가노그래프 키를 보내는 것은 영리할 수 있지만 보낸 사람이 받는 사람과 받는 사람만 그러한 메시지의 존재를 알고 있고 추출하는 방법을 알고 있다는 확신이 없으면 쓸모가 없습니다. 실제로 데이터에서 키를 추출하는 방법에 대한 설명과 함께 메시지의 존재에 대한 인식은 그 자체로 키의 유형이며, 이는 다시 처음으로 돌아가게 합니다.

솔루션은 암호화 매개변수가 원본 메시지를 실행 가능하게 해석하기에 충분하지 않은 암호 시스템을 고안하고 ^[1] 메시지를 해석할 수 있는 매개변수를 스스로 유지하는 것입니다. 우리는 그 매개변수를 개인 키라고 부릅니다. 개인 키를 기반으로 새 매개변수 자체가 개인 키가 무엇인지 밝히지 않고도 암호화 도구에 대한 매개변수 세트를 실행 가능하게 생성할 수 있습니다. 해당 매개변수 집합은 공개적으로 공유될 수 있습니다. 한 사람만 해독할 수 있는 한 누가 무엇을 암호화할 수 있는지는 그다지 중요하지 않기 때문입니다. 이 암호화 도구의 매개변수 집합을 공개할 수 있으므로 이를 공개 키라고 합니다.

암호화 및 복호화 키가 다르고 전자를 사용하여 후자를 추론할 수 없는 암호화를 비대칭 암호화라고 하는 반면 대칭 암호화는 키가 같거나 서로 쉽게 추론될 때 사용하는 것입니다.

Alice는 Bob에게 그녀만이 복호화할 수 있는 것을 암호화하는 데만 사용할 수 있는 공개 키(그녀가 개인적으로 보관하는 개인 키로 사용)를 Bob에게 보내고, 반대로 Bob은 Alice에게 사물을 암호화하는 데만 사용할 수 있는 그의 공개 키를 보냅니다. 그 자신만이 해독할 수 있습니다(그가 또한 개인적으로 보관하는 개인 키를 통해). 그러나 정확한 역 알고리즘을 추론할 수 없는 암호화 알고리즘에 대한 매개변수를 어떻게 게시할 수 있습니까?

그 해답은 프로그래밍과 가장 밀접한 수학 분야인 계산 복잡도 이론에 있습니다. 수학적 문제에 대해 충분히 깊이 파고든 사람이라면 누구나 한 가지 방법으로는 수행하기 쉽지만 역방향으로는 수행하기 어려운 변환에 대해 들어본 적이 있을 것입니다. 예를 들어, 미적분학에서 교과서 도함수를 찾는 것은 일반적으로 간단한 연습인 반면, 역함수를 수행하려면(예를 들어 약간 사소하지 않은 적분 또는 교과서 물리적 ODE 또는 PDE를 푸는 것과 같이) 다음을 수행하는 함수 패밀리를 먼저 가정하는 보다 조사적인 과정이 필요합니다. 솔루션을 포함하고 역 문제를 해결하여 이러한 패밀리에서 솔루션을 찾는 것이 보장됩니다(또는 최소한 그럴듯합니다).

RSA 암호 시스템에서 실제로 활용되는 예는 큰 소수를 곱하는 것과 요인을 미리 알지 못한 채 결과 제품을 인수분해하는 것입니다. 곱셈을 하는 것은 사소하지만 인수분해를 하려면 수백 자릿수를 가진 소인수를 무작위로 추측해야 합니다 ^[2] . 작업의 중요한 속성은 확장이 잘 되어야 한다는 것입니다. RSA의 소수 크기에 몇 자릿수를 추가하면 암호화 프로세스에 약간의 복잡성이 추가되는 동시에 크랙에 수천 배 더 많은 작업이 필요한 키가 됩니다. 아주 대략적으로 말하면, 소수의 곱은 암호화에 사용되는 반면, 한 쌍의 소인수는 암호 해독에 사용됩니다.

이 모든 것을 염두에 두고 SRVB 암호 시스템이 어떻게 작동하는지 살펴보겠습니다.

기본 알고리즘 - SRVB 살펴보기

부분집합 문제

다른 공개 키 암호 시스템과 마찬가지로 SRVB는 생성하기 쉬운 특정 문제를 해결하는 어려움에 의존합니다. SRVB의 경우 다음과 같이 설명할 수 있는 부분집합 합계 문제입니다.

정수 $w$와 $v_1, \cdot \cdot \cdot, v_N \in Z$가 주어졌을 때 $ \sum_ {i = 1}^{N} v_i b_i = w $.

분명히 이 문제는 N개의 정수를 무작위로 선택하고 그 중 일부를 무작위로 선택하고 이 하위 집합을 합산하여 생성할 수 있습니다. 이는 사소한 일입니다.

무차별 대입 검색은 $ O( N * 2^N ) $의 복잡성을 가지며 $b$s 값의 각 조합을 계산합니다. 더 효율적인 접근 방식은 1972년 Horowitz와 Sahni에 의해 $ O ( N * 2 ^ {N / 2} ) $의 복잡성으로 제공되었습니다. 문제는 $b$s와 $w$를 $k$ 차원의 정수 벡터로 대체하는 것만큼 어렵습니다. 그러나 이 더 어려운 문제가 있는 영역은 아래에서 볼 수 있듯이 동일한 문제의 더 쉬운 버전이 발생하는 링과 동형도 있어야 합니다. 이러한 이유로 SRVB는 $ k = 2 $인 가우스 정수 내의 부분집합 합계 문제를 이용합니다.

탐욕 알고리즘을 사용하여 이 문제를 쉽게 계산할 수 있는 특별한 경우가 있습니다. 시퀀스 스케일링 인수 $ v_1, \cdot \cdot \cdot, v_N $를 정렬하면 시퀀스의 각 정수가 그 앞에 오는 모든 정수의 합보다 더 큽니다($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), 선형 시간에서 시퀀스 b 를 찾기 위해 욕심 많은 접근 방식을 사용할 수 있습니다. 설명된 속성을 가진 시퀀스를 슈퍼 증가 시퀀스 라고 합니다.

다음은 이 경우에 대한 탐욕스러운 솔루션에 대한 간단한 설명입니다.

$ i = N $, 현재 관찰된 요인으로 시작하고 $ w' = w $, $w$의 나머지
현재 스케일링 계수가 $w$의 나머지 부분에 맞지 않으면 $ v_i > w'$를 의미하며 $b_i = 0$을 설정하고 다음 단계를 계속합니다. 그렇지 않으면 스케일링 인자가 순서에 있어야 한다는 것을 알고(나머지 인자가 $v_i$보다 작기 때문에) $b_i = 1$로 설정합니다.
$ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. $i > 0$이면 2단계로 돌아갑니다.
이제 $w' == 0$인지 확인하십시오. 그렇지 않으면 문제가 손상되었습니다.

이것은 현재 관찰된 것보다 작은 모든 승수가 현재 승수가 할 수 있는 만큼 (하위)합 $ w' $를 집합적으로 포함할 수 없다는 것을 알고 있기 때문에 작동합니다. 따라서 나머지 합계가 현재 요소보다 크면 다음 모든 요소가 현재 요소의 도움 없이 합산되지 않을 것임을 확실히 알고 있습니다. 반면에 모든 승수는 양수이므로 현재 인수 $ v_i $가 나머지 합계 $ w' $보다 크면 다른 인수를 추가하면 결과가 $ w' $를 훨씬 초과하게 됩니다.

기사의 나머지 부분에 대한 표기법을 설정해 보겠습니다. 우리는 $ v_1, \cdot \cdot \cdot, v_n $ 및 $w$를 수퍼 증가 시퀀스의 인수와 합으로 선택하고 $ u_1, \cdot \cdot \cdot, u_n $ 및 $y$는 공개적으로 $ b_1, \cdot \cdot \cdot, b_n $을 복구하기 위해 제공되는 사용 가능한 매개변수.

시퀀스 $ u_1, \cdot \cdot \cdot, u_n $가 선택되어 초과 증가하지 않고 숫자 $y$가 공개적으로 사용 가능하므로 시퀀스 $ b_1, \cdot \cdot \cdot를 복구하기에 충분한 정보가 공개적으로 제공되지 않습니다. , b_n $. 그러나 시퀀스 $ u_1, \cdot \cdot \cdot, u_n $를 대신할 수 있는 $ v_1, \cdot \cdot \cdot, v_n $이 증가하는 시퀀스가 있으면 이 시퀀스를 사용하여 다음 문제를 해결할 수 있습니다. 탐욕스러운 접근.

아래에서 그것이 어떻게 작동하는지 보여줄 것입니다.

이전 암호 시스템에서 부분집합 사용

1978년에 Ralph Merkle와 Martin Helman은 이전 섹션에서 설명한 두 시퀀스 간의 연결을 구축하기 위해 두 배낭 패러다임과 모듈러스 연산의 선형성을 활용하는 방법을 고안하여 공개 키 암호 시스템을 구상했습니다. 아이디어는 비밀 피연산자가 있는 선형 연산(모듈러스)을 사용하여 쉬운 배낭 (정수 증가 벡터로 구성된 배낭)을 어려운 배낭(이 속성이 없는 배낭)으로 변환하는 것이었습니다. 변환은 모든 $v_i$에 $\theta$를 곱하고 이 곱의 나머지를 $\alpha$로 취하는 것으로 구성됩니다. 여기서 $\alpha \gt \sum_{i=1}^N v_i$ 및 $\gcd (\alpha, \theta) = 1$ (곧 정당화될 두 가지 제약 조건). 결과 $u_1, \ldots, u_N$ 시퀀스는 더 이상 증가하지 않으며 하드 배낭 으로 간주될 수 있습니다.

시퀀스 $u_1, \ldots, u_N$의 무작위 순열은 암호화하여 우리에게 메시지를 보내려는 당사자에게 주어집니다. 순열은 제3자가 원래의 초과 증가 시퀀스가 무엇인지 추측하기 어렵게 하기 위해 수행됩니다. 메시지의 비트 블록은 계수 $b_1, \ldots, b_N$로 사용됩니다. 암호화는 키 시퀀스에 이 계수 시퀀스를 곱하고 곱셈을 결과로 합산하여 수행되며 $y$라는 레이블이 지정됩니다. 개인 키의 소유자만이 $y$를 $b_1, \ldots, b_N$ 블록에 쉬운 정수 ($v_1, \ldots 시퀀스)를 곱하면 얻을 수 있는 해당 $w$로 변환할 수 있습니다. , v_N$). 이것은 $y$에 $\theta^{-1}$를 곱하는 방법으로 수행됩니다. $\theta$ 계수 $\alpha$의 곱셈 역(이의 존재는 $\gcd(\alpha, \ 세타) = 1$). 즉, $(\theta * \theta^{-1}) \bmod \alpha = 1$입니다. 그런 다음 $w = (y * \theta^{-1}) \bmod a$를 계산합니다. 이것이 작동하도록 보장되는 이유 는 계수의 선형성 , 즉 나머지의 선형 조합이 선형 조합의 나머지와 동일하기 때문입니다.

$u$의 정의, 몫 링 및 모듈러스 연산자의 선형성 속성을 연속적으로 적용하면 다음과 같은 대응을 볼 수 있습니다.

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ 왼쪽[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

따라서 쉬운 합 $w$는 양쪽에 $\theta^{-1}$를 곱하고 모듈러스를 $\alpha$로 취함으로써 복구될 수 있습니다. 그렇게 하려면 $\alpha$와 $\theta$($\theta^{-1}$를 쉽게 계산할 수 있게 함)를 모두 알아야 하며, 이는 개인 키의 일부로 비공개로 유지되어야 합니다.

$\alpha \gt \sum_{i=1}^N v_i$라는 단일 제약 조건이 정당화되지 않고 여기에 설명이 나옵니다. 정수의 고리 모듈로 $\alpha$. 즉, $\alpha$ 로 나눈 나머지 멤버의 평등을 명시할 뿐이며, 이는 멤버 자체의 평등을 위한 충분 조건이 아닙니다 . 결과적으로 $b$ 값의 하나 이상의 벡터가 단일 $y$에 매핑될 수 있으며, 이는 가능한 최대 부분합(즉, 모든 소포 $v_i$의 합) $w_{max}$을 다음으로 제한함으로써 방지됩니다. $b$ 값의 조합에 대해 $\alpha$보다 작아야 합니다.

일상 생활의 다른 모든 경우와 마찬가지로 모든 가설에 대한 완전한 지식은 종종 불가능하고 결코 쉬운 일이 아닙니다. 결과적으로 우리는 암호화 시스템이 사용하기에 안전한지 판단할 때 수학적 직관에 의존해야 하며, 이는 우리에게 실질적인 보장을 제공하지 않습니다. 생성된 지 6년 후 A. Shamir의 공격으로 MH 암호 시스템이 손상되었습니다. MH를 되살리려는 시도가 몇 번 더 있었지만 대부분 실패했습니다.

Santana Rocha - Villas Boas(SRVB) 암호화 시스템

2016년에 이 기사의 저자와 다른 영감을 받은 ^[3] 암호 시스템 가능성에 대해 몇 차례 브레인스토밍을 한 후 Daniel Santana Rocha는 $\theta$와 $\alpha$를 가우시안 정수로 대체하는 아이디어를 냈습니다. 보다 기술적인 이유로 이 접근 방식은 앞서 언급한 Shamir 공격에 대한 저항으로 이어집니다.

그는 또한 이전에 설명된 단단한 배낭 의 선형 조합의 여러 단계로 구성된 비트 블록을 생각했습니다. 각각에서 이전의 모든 합계보다 높은 1에 해당하는 새로운(가우시안) 정수가 시퀀스 끝에 추가되고 현재 가장 작은 정수는 삭제됩니다.

다르면서도 우아하게 유사한 제약 조건이 $\alpha$에 적용되며, 이는 이제 가우스 정수입니다. $w_{max} \leq \vert\alpha\vert^2$가 필요합니다. 그 이유는 공식화하기가 매우 어렵지만 다행히도 다음과 같은 우아한 설명에서 쉽게 직감할 수 있습니다.

복소수의 평면에서 정사각형 격자를 상상해보십시오. 그 측면은 실제 축과 가상 축에 평행한 catheti a와 b의 직각 삼각형의 빗변입니다. 그러한 격자의 예가 아래에 나와 있습니다. Guassian integers modulo $\alpha = a + bi$는 그러한 격자 내에 위치한 점으로 나타낼 수 있습니다. 이러한 격자 내에는 $\vert\alpha\vert^2$ 별개의 점이 있습니다. 충분히 큰 $\alpha$를 선택하면 쉬운 배낭의 모든 선형 조합을 맞출 수 있습니다.

이것은 동형사상 $f : Z/n \rightarrow Z[i]/(\alpha)$의 그래픽 표현입니다. 여기서 $n = 13$이고 $\alpha = a + bi = 3 + 2i$입니다($ n$ 및 $\alpha$는 실제로 $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $를 필요에 따라 충족합니다. 점은 가우스 정수, 즉 $a$와 $b$가 정수인 복소수 $a + bi$를 나타냅니다. 평소와 같이 가로축은 실수부를 나타내고 세로축은 허수부를 나타냅니다. 따라서 한 점을 오른쪽 또는 왼쪽으로 이동하는 것은 현재 값에 각각 +1 또는 -1을 추가하는 것과 같습니다. 마찬가지로, 한 점을 위 또는 아래로 이동하는 것은 각각 +i 또는 -i를 추가하는 것과 같습니다.

빨간 점은 $0 \bmod(\alpha)$에 해당합니다. 이 외에도 4쌍의 점을 더 색칠했습니다.

색깔	… mod α와 동일
주황색	$1$
녹색	$i$
푸른	$-1-i$
제비꽃	$1-i$

동형 $f$는 순환 시퀀스 $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$는 다음 규칙을 따르는 그림의 순환 점 시퀀스의 $i$th 요소에 추가합니다.

첫 번째 행의 빨간 점에서 시작합니다.
수평 오른쪽 화살표를 따릅니다. 그거 빼고
화살표를 따라가면 격자 외부의 시퀀스가 리드할 때 검정색이 아닌 점 중 하나에 도달합니다. 그 지점으로 가는 대신, 같은 사각형 안에 있는 같은 색깔의 지점으로 점프합니다. 그리고 마지막으로
이 비검정 점이 빨간색이 되면(다른 모든 색상이 통과된 후 발생) 시퀀스가 가장 높은 빨간색 점으로 점프하여 주기를 다시 시작합니다.

$Y$ 이상의 자연 정수를 매핑하려면 $\vert\alpha\vert^2$ 면적의 정사각형을 가져와야 합니다(여기서 $\vert\alpha\vert = \sqrt{a^2 + b^2} $는 피타고라스의 정리에 의해 측면의 척도) 최소한 높은 것입니다.

각 "점프"는 행 번호를 $r$에서 $r \leftarrow (r + b)(mod a + b)$로 변경하고, 행을 위에서 아래로 세는 경우 $r \leftarrow (r + a)(mod a + b)$ 하나가 아래에서 위로 계산되는 경우. 따라서 각 행(및 점)이 각 주기에서 정확히 한 번 로밍되기 위한 필요 충분 조건은 점프 크기가 행 수와 동소(coprime), 즉 $gcd(a,a + b) = gcd(b,a + b) = 1$. 최대공약수 연산자의 속성으로 인해 이 둘은 모두 $gcd(a,b) = 1$와 같습니다.

YS Villas Boas는 $a$와 $b$의 공약성의 필요성을 알아차렸습니다. 초과 증가를 유지하기 위해 시퀀스 끝에 추가된 각각의 새로운 정수 $w$는 현재 모든 정수의 합을 초과해야 합니다($w > \sum_{i=1}^k v_i$). 그는 이것을 달성하기 위해 그들의 곱셈 계수 $b_i$는 적어도 1이어야 하고, 따라서 각 비트는 계수 0과 1에 매핑될 수 없다는 것을 관찰했습니다. 계수가 0과 1이면 블록만 1개로만 구성되어 있으면 초증가성을 만족시킬 것입니다. 이러한 이유로 비트 0과 1은 곱셈 계수 1과 2에 각각 매핑되었습니다.

마지막으로, 덜 간단합니다. 디코딩의 각 단계에서 하나의 새로운 정수 $v_1$가 방정식 $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n}의 해로 발견됩니다. b_i v_i$, 여기서 모든 $v_i$ 및 $b_i$는 $1 < i \leq n$로 알려져 있습니다. 우리는 $b_1$도 모르기 때문에 하나의 방정식과 두 개의 변수가 있는 시스템으로 끝납니다. 이를 수정하려면 항상 $b_1$에 할당되도록 하나의 양수 값(간단함을 위해 1)을 중재해야 하므로 모호성을 제거해야 합니다. 따라서 첫 번째 계수는 1로 고정되어 있으므로 각 단계에서 $n$ 비트를 인코딩하려면 정수 시퀀스의 길이가 $n + 1$ 요소여야 합니다.

해결해야 할 마지막 기술은 메시지의 바이트 크기가 블록 크기의 배수가 아닌 경우입니다. 다시 말해, 데이터 블록이 복구되면 원래 콘텐츠의 모든 바이트가 보존되지만 그 이상은 유지되지 않도록 마지막 데이터 블록의 가능한 남은 바이트를 어떻게 처리해야 할까요? 메시지의 마지막 바이트를 한 번 반복하여 해결했습니다. 이 사본 다음에는 각 구성 요소가 이전 구성 요소와 다르기만 하면 되는 임의의 시퀀스가 옵니다. 따라서 데이터 블록이 검색될 때 데이터 블록의 마지막 또는 최악의 경우 마지막 바이트 반복에서 마지막 이전 블록이 잘립니다. ^[4]

이제 SRVB 암호 시스템의 예를 보여 드리겠습니다.

매개변수로 시작합니다.

$k = 4$;

$m = 4$;

이것은 $l = 4 * 4 = 16$의 블록 길이와 $k + 1 = 5$ 자연 정수의 수퍼 증가 시퀀스를 생성합니다 . 즉, 선형 결합되고 이 선형 결합의 결과가 추가됩니다. 마지막 $k + 1$ 요소로 축소 —$m = 4$ 번;

단순화를 위해 다음을 $v_i$의 (초증가) 벡터로 둡니다.

$(1,2,4,8,16)$

실제로, 2의 처음 다섯 거듭제곱의 시퀀스는 이것이 5개의 요소와 가장 작은 엄격하게 양의 가능한 값을 갖는 수퍼 증가 시퀀스이기 때문에(따라서 공개 키에서 0을 피하여 해당 상대의 해당 0을 사소하게 제공합니다) ).

앞에서 말했듯이 $\alpha = a + bi$의 경우 정수 $a$와 $b$는 소소수여야 하며, 우리가 언급한 새로운 제약 조건에 따라 $a^2 + b^2를 요청해야 합니다. = \vert\alpha\vert^2 \geq W$. 빠르게 계산하면 $W = 1590$가 됩니다. $\sqrt{1590} \simeq 39.8$ 이후로 매우 편리한 $\alpha$를 선택하면 $\alpha = 39 + 40i$가 됩니다. $gcd(a,b)=1$도 만족하면서 최소 1590개의 구성 요소. 또한 $gcd(a,\theta)=1$ ^[5] 가 되도록 $\theta$를 선택해야 하며 바람직하게는 너무 낮지 않도록 $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (또한 정보 제공을 피하기 위해). $\theta = 60$는 다음을 산출합니다.

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

그럼 손을 더럽히자. Hello Toptal! . 먼저 ASCII 및 데이터 블록 자르기 규칙에 따라 바이트 배열에 매핑합니다.

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

우리의 데이터 블록은 16비트 = 2바이트 길이이고 메시지에는 13개의 문자가 있기 때문에 각각 2바이트의 7개 데이터 블록으로 끝납니다. 여기서 마지막 블록은 '!' . 첫 번째 블록을 단계별로 암호화해 보겠습니다. 각 바이트의 비트가 의미 있는 순서대로 취해지기 때문에 세심한 주의를 기울이십시오.

$m=01001000 01100101$

첫 번째 바이트의 첫 번째 니블: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
첫 번째 바이트의 두 번째 니블: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
두 번째 바이트의 첫 번째 니블: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
두 번째 바이트의 두 번째 니블: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

따라서 우리는 방금 매핑했습니다.

"그" $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

나머지 암호화된 메시지는 다음과 같습니다.

"일" $\오른쪽 화살표(12-12i,21-2i,61-3i,185-31i,367-59i)$

"o" $\오른쪽 화살표(12-12i,25+33i,65+32i,111+44i,244+124i)$

"끝" $\오른쪽 화살표(12-12i,9+10i,46+12i,149+5i,277+31i)$

"pt" $\오른쪽 화살표(12-12i,3+16i,46+12i,73+23i,201+49i)$

"알" $\오른쪽 화살표(12-12i,4+54i,44+53i,117+193i,231+389i)$

"!!" $\오른쪽 화살표(12-12i,4+54i,32+65i,63+92i,121+247i)$

이제 해독을 위해 $\theta^{-1}=60^{-1}=27+i$가 있습니다.

$($"그" $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223,527)$

이제 욕심 많은 알고리즘이 나옵니다.

먼저 각 기여 요인에 1을 곱한 값을 뺍니다. 왜냐하면 그들이 마지막에 한 번 이상 기여한 것으로 알려져 있기 때문입니다.

두 번째 바이트의 두 번째 니블:

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = 거짓 \오른쪽 화살표 b_1=0 ; T \왼쪽 화살표 (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = 참 \오른쪽 화살표 b_2 = 1; T \왼쪽화살표 (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = 참 \오른쪽 화살표 b_3 = 1; T \왼쪽화살표 (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = 거짓 \오른쪽 화살표 b_4 = 0; T \왼쪽 화살표 (T - 0 * 16) = 8$

결과: 0110;

나머지: 8(최하위 새로운 요소로 시퀀스의 시작 부분에 추가됨);

현재 시퀀스의 마지막에서 527을 삭제합니다.

두 번째 바이트의 첫 번째 니블:

$T \왼쪽화살표 (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = 거짓 \오른쪽 화살표 b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = 참 \오른쪽 화살표 b_2 = 1; T \왼쪽 화살표 (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = 거짓 \오른쪽 화살표 b_3 = 0; T \왼쪽 화살표 (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = 참 \오른쪽 화살표 b_4 = 1; T \왼쪽 화살표 (T - 0 * 12) = 4$

결과: 0101;

나머지: 4(최하위 새로운 요소로 시퀀스의 시작 부분에 추가됨);

현재 시퀀스의 마지막에서 233을 삭제합니다.

첫 번째 바이트의 두 번째 니블:

$T \왼쪽화살표 (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = 거짓 \오른쪽 화살표 b_1 = 0; T \왼쪽 화살표 (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = 참 \오른쪽 화살표 b_2 = 1; T \왼쪽 화살표 (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = 거짓 \오른쪽 화살표 b_3 = 0; T \왼쪽 화살표 (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = 거짓 \오른쪽 화살표 b_4 = 0; T \왼쪽 화살표 (T - 0 * 4) = 2$

결과: 0100;

나머지: 2(최하위 새로운 요소로 시퀀스의 시작 부분에 추가됨);

현재 시퀀스의 마지막에서 93을 삭제합니다.

첫 번째 바이트의 첫 번째 니블:

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = 참 \오른쪽 화살표 b_1 = 1; T \왼쪽화살표 (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = 거짓 \오른쪽 화살표 b_2 = 0; T \왼쪽화살표 (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = 거짓 \오른쪽 화살표 b_3 = 0; T \왼쪽화살표 (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = 거짓 \오른쪽 화살표 b_4 = 0; T \왼쪽화살표 (T - 0 * 2) = 1$

결과: 1000;

나머지: 1(최하위 새로운 요소로 시퀀스의 시작 부분에 추가됨);

현재 시퀀스의 마지막에서 47을 삭제합니다.

결과적으로 메시지의 처음 두 문자 "He"가 포함된 "01001000 01100101" 데이터 블록을 복구했습니다. 뿐만 아니라 개인 키 증가 시퀀스 $(1,2,4,8,16)$도 올바르게 검색했습니다.

다른 데이터 블록 맵도 같은 방식으로 진행됩니다.

주요 공개키 암호시스템과의 비교

SRVB는 다음과 같습니다.

완전 무료 및 공개;
ECC보다 훨씬 더 간단하고 이해하고 구현하기 쉽습니다 ^[7] ;
예를 들어 값이 비싼 소수에 의존하는 RSA와 달리 키가 풍부하여 사실상 비용이 들지 않습니다.

우리는 이미 가장 가능성이 높은 취약점을 요약할 수 있습니다. SRVB는 MH의 후손이기 때문에 Shamir 공격의 일반화나 이를 깨뜨리는 다른 공격에 취약할 것이라고 의심하기 쉽습니다. 저자는 이것이 사실이 아닐 것이라고 믿을 만한 이유가 있었지만 아직 확인되지 않았습니다(암호화 시스템을 다룰 때 매우 일반적임).

무엇 향후 계획?

Rocha는 사용되는 몫 고리에 대한 몇 가지 일반화를 관찰했으며, 이는 암호 분석의 복잡성을 증가시킬 수 있습니다. 우리는 이러한 가능성도 조사할 것입니다.

선형 대수 모호화

SRVB의 개발 및 문서화 과정에서 Villas Boas는 배낭 공개 키 암호 시스템의 개념을 개선하기 위한 또 다른 접근 방식을 생각해 냈습니다. 지루하지만 여기 훑어보기가 있습니다. 파악에 실패하더라도 걱정하지 마십시오. 다음 기사에서 계속해서 자세히 살펴보겠습니다. 다음 기사에서 다음 기사의 하위 집합 합계 $y$를 참조하세요. $N$ 몫 링 요소 $u_i$(이전과 같이 슈퍼 증가 시퀀스의 양의 정수 $v_i$에 동형적으로 해당)는 이러한 $u_i$의 행 벡터를 열 벡터 $B$로 곱한 것입니다. 이진법) 0과 1의 경우 ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

여기서 $b_i \in {0,1}$

이제 $u_i$의 벡터 대신 왼쪽에 $n$ x $N$($n < N$ 포함) 행렬 V가 있고 $v_i$(초증가의 정수 시퀀스) 벡터를 (일반성을 잃지 않고) 첫 번째 행과 노이즈로 채워진 다른 모든 항목으로 사용합니다. 이제 V에 동일한 비트 벡터 B를 곱하면 $w$가 첫 번째 항목으로 포함되고 나머지 항목에는 노이즈가 있는 열 벡터 W가 제공됩니다. 이제 이 V 행렬을 취하고 왼쪽에 있는 임의의 ^[9] n x n 행렬 R을 곱하여 n x N 행렬 P를 정의합니다.

피 = RV

아이디어는 Bob이 P를 새 공개 키로 사용한다는 것입니다. R의 무작위성 때문에 벡터는

$Y = PB = RV B = RW$

V의 다른 행에 있는 노이즈에 의해 정보가 가려진 $w$가 있습니다. 또한 Bob은 다음을 충족하는 행 벡터 S를 미리 계산하고 저장합니다.

$R^TS^T = e_1$

Alice가 Y를 Bob에게 보낼 때 그는 다음과 같은 이유로 SY를 찾습니다.

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(지금까지는 정의만)

${e_1}^T(VB)={e_1}^TW = w$

(이제, Rs를 취소하기 위해 연관성을 이용함)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

감사의 말

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

용어 사전

Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.