선형 피드백 시프트 레지스터. 선형 반복 레지스터

피드백 시프트 레지스터( FSR ) 두 부분으로 구성됩니다. 시프트 레지스터그리고 피드백 기능 .

시프트 레지스터(오류: 참조 소스를 찾을 수 없음)는 일련의 비트입니다. 비트를 추출해야 하는 경우 시프트 레지스터의 모든 비트가 오른쪽으로 1 위치 이동됩니다. 새로운 맨 왼쪽 비트는 레지스터의 나머지 비트에서 피드백 기능의 값입니다. 기간 시프트 레지스터는 반복을 시작하기 전 결과 시퀀스의 길이입니다.

피드백 시프트 레지스터의 가장 간단한 유형은 다음과 같습니다. 피드백이 있는 선형 시프트 레지스터(LFSR – 왼쪽 피드백 옮기다 등록하다) (오류: 참조 소스를 찾을 수 없음). 피드백은 단순히 일부 p 비트의 XOR입니다. 레지스터, 이러한 비트의 목록을 호출합니다. 바이패스 시퀀스.

N-bit LFSR은 다음 중 하나일 수 있습니다. 2 N -1 내부 상태. 이는 이론적으로 이러한 레지스터가 주기를 가진 의사 난수 시퀀스를 생성할 수 있음을 의미합니다. 2 N -1 비트. 내부 상태의 수와 기간은 동일합니다. 레지스터를 0으로 채우면 무한한 0 시퀀스가 ​​생성되기 때문입니다. 이는 전혀 쓸모가 없습니다. 특정 탭 시퀀스에서만 LFSR은 모든 탭 시퀀스를 순환합니다. 2 N -1 내부 상태. 이러한 LFSR은 LFSR최대 기간으로.

특정 LFSR이 최대 주기를 갖기 위해서는 탭 시퀀스와 상수로 구성된 다항식 1 프리미티브 모듈로여야 합니다. 2 .

다항식의 원시성을 계산하는 것은 상당히 복잡한 수학적 문제입니다. 따라서 발전기의 최대 기간을 제공하는 탭 시퀀스의 수를 나열하는 기성품 표가 있습니다. 예를 들어 32비트 시프트 레지스터의 경우 다음 항목을 찾을 수 있습니다. (32,7,5,3,2,1,0) . 즉, 새 비트를 생성하려면 XOR 함수를 사용하여 30초, 7번째, 5번째, 3번째, 2번째 및 1번째 비트를 합산해야 합니다.

C++에서 이러한 LFSR에 대한 코드는 다음과 같습니다.

// 0이 아닌 모든 값

시프트레지스터 = ((((시프트레지스터 >> 31)

^(시프트레지스터>>6)

^(시프트레지스터>>4)

^(시프트레지스터>>2)

^(시프트레지스터>>1)

^쉬프트레지스터)

& 0x00000001)<<31)

| (시프트레지스터 >> 1);

ShiftRegister & 0x00000001을 반환합니다.

LFSR의 소프트웨어 구현은 C가 아닌 어셈블러로 작성된 경우 매우 느리고 더 빠르게 실행됩니다. 한 가지 솔루션은 16개의 LFSR을 병렬로 사용하는 것입니다(또는 특정 컴퓨터 아키텍처의 단어 길이에 따라 32개). 이 체계에서는 LFSR의 길이와 같은 크기의 단어 배열을 사용하고 배열의 각 단어 단위는 자신의 LFSR을 참조합니다. 동일한 탭 시퀀스 번호를 사용하면 눈에 띄는 성능 향상을 얻을 수 있습니다.

와 함께 피드백 회로도 수정할 수 있습니다. 이 경우 생성기의 암호화 강도가 더 높지는 않지만 프로그래밍 방식으로 구현하는 것이 더 쉬울 것입니다. 탭 시퀀스 비트의 가장 왼쪽 비트를 사용하여 새 비트를 생성하는 대신 탭 시퀀스의 각 비트를 생성기의 출력과 XOR하고 이 작업의 결과로 대체하면 생성기 결과가 새로운 가장 왼쪽 비트가 됩니다( 오류: 참조 소스를 찾을 수 없음).

이 수정은 갈루아 구성. C언어에서는 다음과 같이 보입니다.

정적 부호 없는 긴 ShiftRegister = 1;

void seed_LFSR(부호 없는 긴 시드)

ShiftRegister = 시드;

int Galua_LFSR(무효)

if (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ 마스크 >> 1) | 0x8000000;

시프트레지스터 >>= 1;

결론은 모든 XOR이 하나의 작업으로 수행된다는 것입니다. 이 회로도 병렬화할 수 있습니다.

LFSR은 그 자체로 좋은 의사 난수 시퀀스 생성기이지만 일부 바람직하지 않은 비무작위 속성이 있습니다. 순차 비트는 선형이므로 암호화에 쓸모가 없습니다. LFSR 길이의 경우 N내부 상태는 이전 상태를 나타냅니다. N발전기 출력 비트. 피드백 방식이 비밀로 유지되더라도 다음을 통해 결정할 수 있습니다. 2 N특수 알고리즘을 사용하는 생성기 출력 비트. 또한 이 시퀀스의 연속 비트를 사용하여 생성된 큰 난수는 높은 상관 관계가 있으며 일부 유형의 응용 프로그램에서는 무작위가 아닙니다. 그럼에도 불구하고 LFSR은 종종 암호화 알고리즘을 만드는 데 사용됩니다. 이를 위해 일반적으로 길이와 탭 시퀀스 번호가 다른 여러 LFSR이 사용됩니다. 핵심은 레지스터의 초기 상태입니다. 새 비트가 필요할 때마다 모든 레지스터가 이동합니다. 이 작업은 클럭킹. 출력 비트는 LFSR의 일부 비트의 함수, 바람직하게는 비선형입니다. 이 함수는 결합, 그리고 발전기 전체 - 결합 발전기. 이러한 발전기 중 다수는 오늘날에도 여전히 안전합니다.

선형 피드백 시프트 레지스터(RSLOS, 영어. 선형 피드백 시프트 레지스터, LFSR )는 입력(슬라이딩) 비트의 값이 시프트 전 레지스터의 나머지 비트 값에서 선형 부울 함수와 동일한 비트 워드의 시프트 레지스터입니다. 소프트웨어와 하드웨어로 구성할 수 있습니다. 이것은 특히 암호화에 사용되는 '의사 무작위' 시퀀스 비트를 생성하는 데 사용됩니다.

설명

하드웨어 구현에서 레지스터 제어는 시프트 펄스(또는 시계또는 동기화 펄스) 모든 셀에 대해. 소프트웨어 구현에서 레지스터 관리는 루프를 실행하여 수행됩니다. 루프가 반복될 때마다 피드백 함수가 계산되고 워드의 비트가 이동됩니다.

작동 원리

선형 복잡도

상관 독립성

생성된 시퀀스의 높은 선형 복잡성을 얻기 위해 암호 작성자는 여러 시프트 레지스터의 출력을 비선형으로 결합합니다. 이 경우 하나 이상의 출력 시퀀스(또는 개별 LFSR의 출력)를 공통 스트림으로 연결하고 암호 분석가가 열 수 있습니다. 이러한 취약점을 기반으로 한 해킹을 상관관계 열기. 이러한 핵의 주요 아이디어는 생성기의 출력과 구성 요소 출력 간의 상관 관계를 찾는 것입니다. 그런 다음 출력 시퀀스를 관찰하여 이러한 중간 출력에 대한 정보를 얻을 수 있으므로 생성기를 해킹할 수 있습니다. Thomas Siegenthaler는 상관 독립성을 정확하게 정의하는 것이 가능하며 상관 독립성과 선형 복잡성 사이에 균형이 있음을 보여주었습니다.

소프트웨어 구현

RSLOS의 소프트웨어 구현은 상당히 느리고 어셈블러로 작성된 경우 더 빠르게 작동합니다. 솔루션 중 하나는 16개의 RLLS(또는 컴퓨터 아키텍처의 단어 길이에 따라 32개)를 병렬로 사용하는 것입니다. 이러한 방식에서는 크기가 시프트 레지스터의 길이와 동일한 워드 배열이 사용되며 워드의 각 비트는 자체 LFSR을 참조합니다. 동일한 수의 탭 시퀀스가 ​​사용되기 때문에 발전기 성능이 눈에 띄게 향상될 수 있습니다.

피보나치 구성

32비트 시프트 레지스터를 고려하십시오. 이스케이프 시퀀스가 ​​있습니다. (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)). 즉, 새로운 비트를 생성하려면 XOR 연산을 사용하여 31, 30, 29, 27, 25, 0번째 비트를 합산해야 합니다. 결과 LFSR에는 최대 기간이 있습니다. 2 32 − 1 (\디스플레이스타일 2^(32)-1). C에서 이러한 레지스터에 대한 코드는 다음과 같습니다.

int LFSR_Fibonacci (void) (정적 부호 없는 long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25 ) ^ S ) & 0x00000001 )<< 31 ) | (S >> 1); 반환 S & 0x00000001 ; )

갈루아 구성

이 생성기는 암호화 강도가 더 높지는 않지만 성능 향상을 제공합니다. 병렬화를 통한 모든 XOR 연산은 피보나치 구성에서와 같이 순차적으로 수행되는 것이 아니라 한 연산에서 수행될 수 있습니다. 이 체계는 또한 하드웨어 구현에서 이점을 제공합니다.

C에서 32비트 시프트 레지스터에 대한 코드는 다음과 같습니다.

int LFSR_Galois (void) (정적 부호 없는 long S = 0x00000001 ; if (S & 0x00000001 ) ( S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; 1 반환;) else ( S >>= 1 ; 반환 0 ;) )

Galois 구성에서 LFSR_Galois 함수에 대한 고정된 수의 호출 주기는 Fibonacci 구성(Intel Core i5의 MS VS 2010 컴파일러)의 LFSR_Fibonacci 함수보다 약 2배 더 빠릅니다.

생성된 시퀀스 예

피보나치 구성

LFSR을 다음과 같은 특성 다항식으로 지정합니다. x 3 + x + 1 (\displaystyle x^(3)+x+1). 이것은 탭 비트가 2번째와 0번째가 된다는 것을 의미하며, 다항식의 단위는 0번째 비트가 입력이라는 것을 의미합니다. 피드백 기능의 형식은 다음과 같습니다. S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). 시프트 레지스터의 초기 상태가 시퀀스라고 가정합니다. 레지스터의 추가 상태는 아래 표에 나와 있습니다.

일곱 번째 단계에서 내부 상태가 원래 상태로 돌아왔으므로 다음 단계부터 비트가 반복됩니다. 따라서 생성된 시퀀스는 다음과 같습니다. [1, 0, 0, 1, 1, 1, 0, 1. . . ] (\디스플레이스타일\왼쪽)(시퀀스의 비트 순서는 LFSR에서 생성된 순서와 일치합니다.) 따라서 시퀀스의 주기는 7, 즉 주어진 다항식의 원시성으로 인해 발생한 최대 가능한 값입니다.

갈루아 구성

동일한 특성 다항식을 취합시다. c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). 첫 번째 비트만 출력 비트에 추가됩니다. 초기 상태는 동일합니다. 레지스터의 추가 상태:

일곱 번째 단계에서 레지스터의 내부 상태가 원래 상태로 돌아왔으므로 주기도 7과 같습니다. 피보나치 구성과 달리 레지스터의 내부 상태가 다른 것으로 나타났지만 생성된 시퀀스는 동일합니다. , 4주기만큼만 이동됨: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\디스플레이스타일\왼쪽)(시퀀스의 비트 순서는 LFSR에서 생성된 순서와 일치합니다.)

기본 다항식 생성

장점과 단점

장점

• LFSR 기반으로 생성된 고성능 암호화 알고리즘(예: 스트림 암호)
• 거의 모든 컴퓨팅 장치의 하드웨어에서 구현되는 더하기 및 곱셈의 가장 간단한 비트 연산만 사용;
• 우수한 암호화 속성(LFSR은 우수한 통계적 속성으로 장기간 시퀀스를 생성할 수 있음)
• 구조로 인해 LFSR은 대수적 방법을 사용하여 쉽게 분석됩니다.

결함

생성된 시퀀스의 암호화 강도를 개선하는 방법

다중 시프트 레지스터가 있는 생성기

이 유형의 생성기는 비트를 생성하는 여러 선형 피드백 시프트 레지스터로 구성됩니다. x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\dots ,\;x_(M,i))각기. 또한 생성된 비트는 일부 부울 함수에 의해 변환됩니다. f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\dots ,\;x_(M ,나))). 이 유형의 생성기에는 레지스터 길이가 있습니다. L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\dots ,\;M), 서로 상소합니다.

이 발전기의 주기는 T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), 어디 L = ∑ i = 1 M L i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- 총 셀 수. 따라서 여러 개의 LFSR을 사용하면 단일 레지스터에 비해 생성된 시퀀스의 주기가 증가하여 생성기의 암호화 강도가 증가합니다. 또한 선형 복잡도 또는 주어진 생성기에 해당하는 가장 짧은 레지스터의 길이를 증가시킵니다. 이러한 레지스터는 생성된 시퀀스를 사용하여 Berlekamp-Massey 알고리즘을 사용하여 찾습니다. 기껏해야 그 길이는 생성된 시퀀스의 기간에 비례합니다.

비선형 변환이 있는 생성기

이러한 생성기의 블록 다이어그램은 이전 생성기의 다이어그램과 다르지 않습니다. 주요 차이점은 변환 장치가 비선형 부울 함수로 제공된다는 것입니다. f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\dots ,x_(M))). 예를 들어, Zhegalkin 다항식은 이러한 함수로 간주됩니다(Zhegalkin 정리에 따르면 모든 부울 함수는 Zhegalkin 다항식으로 고유하게 표현될 수 있음).

비선형 생성기는 다음에서도 구현할 수 있습니다. 비선형 피드백 시프트 레지스터. 그는 줄 수 있습니다 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L)) LFSR보다 더 많은 sequence'maximum'period의 변형.

이 생성기의 암호화 강도는 사용된 함수의 비선형성으로 인해 증가합니다. 원래 상태를 복원하는 알고리즘이 알려져 있지 않기 때문에 생성된 비트 시퀀스에서 레지스터의 상태를 결정하는 것은 복잡한 수학적 문제입니다.

이 방법은 예를 들어 다음에서 사용됩니다. 발전기 Geff그러나 일반화된 Geff 생성기는 상관관계 공격에 의해 손상될 수 있습니다.

시프트 레지스터 타이밍이 다른 생성기

정지 발전기

정지 발전기(English Stop-and-Go, Both-Piper)는 LFOS-1의 출력을 사용하여 LFOS-2의 클록 주파수를 제어하므로 LFSR-2는 LFOS-1의 출력이 특정 시점에 상태를 변경합니다. 당시에는 단위와 같았습니다. 이 계획은 상관 관계 개방에 저항하지 않았습니다.

암호화 강도를 높이기 위해 제안되었습니다. 정지 및 이동 발전기. 길이가 다른 세 개의 시프트 레지스터를 사용합니다. 여기서 LFOS-1은 두 번째 및 세 번째 레지스터의 클록 주파수를 제어합니다. 즉, LFSR-2는 LFSR-1 출력이 1일 때 상태를 변경하고 LFSR-3은 LFSR-1 출력이 0일 때 상태를 변경합니다. 생성기의 출력은 RSLOS-2와 RSLOS-3의 두 출력을 모듈로 추가하는 작업입니다. 이 생성기는 주기가 크고 선형 복잡도가 큽니다. RLOS-1의 상관관계 개방 방법이 있지만 이것이 생성기의 암호화 속성을 크게 약화시키지는 않습니다.

정교한 클럭 방식이 사용됩니다. 양방향 정지 및 이동 발전기, 동일한 길이의 2개의 시프트 레지스터를 사용합니다. 어느 시점에서 RLOS-1의 출력이 t i − 1 (\displaystyle t_(i-1))- 1, 그러면 RLOS-2는 시간에 기록되지 않습니다. t i (\디스플레이스타일 t_(i)). 순간에 RLOS-2의 출력이 t i − 1 (\displaystyle t_(i-1)) 0이고 시간에 t i − 2 (\displaystyle t_(i-2))- 1, 그리고 이 레지스터가 그 시간에 클록되는 경우 t i (\디스플레이스타일 t_(i)), 동시에 RLOS-1은 클럭되지 않습니다. 이 회로의 선형 복잡도는 생성된 시퀀스의 주기와 거의 같습니다.

자가 데시메이팅 생성기

내부 제품이 있는 다중 속도 발진기

이 생성기는 두 개의 시프트 레지스터 RSLOS-1 및 RSLOS-2를 사용합니다. RSLOS-2의 클록 주파수 d (\디스플레이스타일 d) RSLOS-1보다 몇 배 더 많습니다. 이러한 레지스터의 특정 비트는 AND 연산을 사용하여 서로 곱해집니다. 곱셈의 결과는 XOR 연산에 의해 더해지고 출력 시퀀스가 ​​얻어진다. 이 생성기는 선형 복잡도가 높고 통계적 특성이 우수합니다. 그러나 그 상태는 길이의 출력 시퀀스에서 결정될 수 있습니다. L 1 + L 2 + log 2 ⁡ d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), 어디 L 1 (\displaystyle L_(1))그리고 L 2 (\displaystyle L_(2))는 각각 LFOS-1 및 LFOS-2의 길이이며, d (\디스플레이스타일 d)- 클록 주파수의 비율.

골만 캐스케이드

이 회로는 stop-go 생성기의 개선된 버전입니다. 이것은 일련의 LFSR로 구성되며, 각각의 타이밍은 이전 LFSR에 의해 제어됩니다. 당시 RLOS-1의 출력이 t i (\디스플레이스타일 t_(i)) 1이면 RLOS-2가 클럭됩니다. 순간에 RLOS-2의 출력이 t i (\디스플레이스타일 t_(i)) 1이면 RLOS-3이 클럭됩니다. 마지막 LFSR의 출력은 생성기의 출력입니다. 모든 LFSR의 길이가 동일하고 L (\디스플레이스타일 L), 다음에서 시스템의 기간 M (\디스플레이스타일 M) LFSR은 다음과 같습니다. (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), 선형 복잡도는 L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .

이 아이디어는 간단하며 큰 주기, 큰 선형 복잡성 및 우수한 통계적 속성을 가진 시퀀스를 생성하는 데 사용할 수 있습니다. 그러나 불행히도 그들은 부검이라는 부검에 민감합니다. 잠금(eng. 잠금) 때

선형 피드백 시프트 레지스터(LFSR)는 이진 비트의 의사 난수 시퀀스를 생성하기 위한 메커니즘입니다. 레지스터(그림 1)는 초기화 벡터(대부분 비밀 키)에 의해 설정된 여러 셀로 구성됩니다. 레지스터의 동작은 각 비트에서 피드백으로의 연결 여부에 따라 결정됩니다. 피드백 레지스터의 탭은 고정되어 있지 않지만 키의 일부입니다. 다음 단계에서 레지스터 셀의 내용은 오른쪽으로 한 위치 이동하고 XOR 연산의 결과로 남은 1비트는 가장 왼쪽 셀에 배치됩니다.

쌀. 1. 피드백이 있는 선형 시프트 레지스터

최대 암호 감마 주기를 달성하기 위한 자릿수 중시프트 레지스터는 메르센 소수(2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...) 중 하나로 선택되고 내부 링크는 레지스터의 값은 가장 높은 차수의 기약이 없는 기본 다항식에 따라 선택되어야 합니다. 중. 이 경우 암호 감마 주기는 (2 중-1).

LFSR은 소프트웨어와 하드웨어 모두에서 빠르고 쉽게 구현할 수 있습니다. 피드백 비트를 적절하게 선택하면 생성된 시퀀스가 ​​우수한 통계적 속성을 갖습니다. LFSR은 고도로 안전한 시스템 구축을 위한 기본 요소로 사용됩니다.

캐스케이드 레지스터는 한 LFSR의 동작이 캐스케이드에서 이전 LFSR의 동작에 따라 달라지는 방식으로 연결된 LFSR 세트입니다. 이 "종속" 동작은 일반적으로 첫 번째 LFSR에 의해 다음 LFSR의 시프트 카운터를 제어하도록 설정됩니다.

예를 들어, 이전 레지스터의 값이 1이면 레지스터를 한 단계 이동하고, 값이 0이면 레지스터를 두 단계 이동하거나 그렇지 않으면 레지스터를 이동합니다. 이러한 조합이 많으면 매우 높은 보안이 가능합니다.

가장 안전한 시퀀스는 두 LFSR 레지스터 결과 간의 간단한 상호 작용을 기반으로 축소 생성기에 의해 생성됩니다. 한 결과의 비트는 두 번째 결과의 해당 비트가 전체 "스트림 키"의 일부로 사용될지 여부를 결정합니다. 압축 생성기는 간단하고 확장 가능하며 우수한 보안 속성을 가지고 있습니다. 단점은 몇 가지 예방 조치를 취하지 않으면 "스트리밍 키"가 생성되는 속도가 일정하지 않다는 것입니다.

지연이 있는 피보나치 방법널리 사용되는 피보나치 생성기 중 하나는 다음 반복 공식을 기반으로 합니다.

어디 Yk- 범위의 실수

쌀. 2. 라운드 로빈 암호화

DES 출력 피드백 모드는 스트림 암호화에 사용되는 방식과 유사하게 의사 난수를 생성하는 데 사용할 수 있습니다. 각 암호화 단계의 출력은 64비트 값이며 상위 j비트만 암호화를 위해 피드백됩니다. 64비트 출력은 우수한 통계적 속성을 가진 의사 난수 시퀀스를 구성합니다.

ANSI X9.17 표준에 설명된 의사 난수 생성기는 암호학적으로 가장 안전한 의사 난수 생성기 중 하나입니다. 이 기술을 사용하는 애플리케이션에는 금융 보안 및 PGP 애플리케이션이 포함됩니다.

ANSI X9.17 생성기는 다음 부분으로 구성됩니다(그림 3).

1. 입력: 생성기는 두 개의 의사 난수 입력으로 제어됩니다. 첫 번째 입력은 현재 날짜 및 시간의 64비트 표현입니다( DT i) 번호가 생성될 때마다 변경됩니다. 두 번째 입력은 임의의 값으로 초기화되고 의사 난수 시퀀스 생성 중에 변경되는 64비트 초기 값입니다( 바이).

2. 키: 생성기는 2개의 키 K 1 , K 2 가 있는 3개의 3중 DES 모듈을 사용합니다. 세 가지 모두 동일한 56비트 키 쌍을 사용하며, 이 키 쌍은 비밀로 유지되어야 하며 의사 난수를 생성하는 데에만 사용되어야 합니다.

쌀. 3. ANSI X9.17 의사 난수 생성기

피드백 시프트 레지스터시프트 레지스터와 피드백 기능.

그림 19. 피드백 시프트 레지스터.

일반적으로 시프트 레지스터는 링 또는 필드의 일부 요소 시퀀스입니다. 가장 일반적으로 사용 조금시프트 레지스터. 이러한 레지스터의 길이는 비트 수로 표현됩니다. 비트가 검색될 때마다 레지스터의 모든 비트가 한 위치씩 오른쪽으로 이동합니다. 새로운 최상위 비트는 레지스터의 다른 모든 비트의 함수로 계산됩니다. 출력은 일반적으로 최하위 비트입니다. 시프트 레지스터의 기간은 반복을 시작하기 전 출력 시퀀스의 길이입니다.

가장 간단한 유형의 시프트 레지스터는 선형 피드백 시프트 레지스터(LFSR 또는 LRS)입니다. 피드백은 레지스터의 일부 비트에 대한 간단한 XOR 연산입니다. 이 비트 목록이 정의됩니다. 특성 다항식그리고 불렀다 탭 시퀀스. 때때로 이 계획은 호출됩니다. 피보나치 구성.

그림 20. 피보나치 구성의 LFOS.

LFSR의 소프트웨어 구현에서는 수정된 체계가 사용됩니다. 새로운 중요 비트를 생성하기 위해 탭 시퀀스의 비트를 사용하는 대신 XOR 연산이 각 비트에서 생성기의 출력으로 수행되어 이전 비트를 대체합니다. 탭 시퀀스의 비트. 이 수정은 때때로 호출됩니다. 갈루아 구성.

그림 21. Galois 구성의 RLOS.

N-bit LFSR은 2개 중 하나일 수 있습니다. N– 1개의 내부 상태. 이는 이론적으로 이러한 레지스터가 주기가 2인 의사 난수 시퀀스를 생성할 수 있음을 의미합니다. N– 1비트(0으로 채우는 것은 전혀 쓸모가 없습니다). 모든 2 통과 N– 특정 탭 시퀀스에서만 가능한 1개의 내부 상태. 이러한 레지스터를 최대 기간이 있는 LFSR이라고 합니다. LFSR의 최대 주기를 보장하기 위해서는 특성 다항식이 원어모듈로 2. 다항식의 차수는 시프트 레지스터의 길이입니다. 원시 차수 다항식 N- 그런거야 줄일 수 없는약수이지만 약수가 아닌 다항식 엑스디모두에게 + 1 디, 이는 2의 약수입니다. N– 1. (다항식을 논의할 때, 용어 소수용어로 대체 기약 다항식). 그림에 표시된 LFSR의 특성 다항식:

엑스 32 + 엑스 7 + 엑스 5 + 엑스 3 + 엑스 2 + 엑스 + 1

프리미티브 모듈로 2입니다. 이러한 레지스터의 기간은 최대이며 반복될 때까지 2 32 - 1 값을 모두 순환합니다. 가장 일반적으로 사용되는 것은 얇은 다항식입니다. 몇 가지 계수만 있습니다. 가장 인기있는 삼항식.

LFSR 기반 생성기의 중요한 매개변수는 선형 복잡성. 길이로 정의된다. N생성기 출력을 시뮬레이션할 수 있는 가장 짧은 LFSR. 선형 복잡도는 단순하기 때문에 중요합니다. Berlenkamp-Massey 알고리즘 2개만 확인하여 이러한 LFSR을 다시 생성할 수 있습니다. N감마 비트. 원하는 LFSR을 정의하면 스트림 암호가 실제로 깨집니다.

LFSR 외에도 비선형 피드백, 전송 피드백 등이 있는 시프트 레지스터도 사용됩니다.

수론적 접근 방식(Blum-Micali 생성기, RSA, BBS, 압축, 추가 생성기 등)을 기반으로 여러 생성기가 개발되었습니다.

스트림 암호화 알고리즘의 합성에 대한 수학적 지원은 블록 암호화 알고리즘과 비교하여 보다 완전하고 상세하게 개발되었습니다. 그러나 스트림 암호를 생성하기 위해 OFB 또는 CFB 모드의 블록 암호 알고리즘이 자주 사용됩니다.

피드백 함수의 가장 간단한 종류는 특정 비트 내용의 모듈로 2 합계와 같은 선형 함수입니다. 이러한 레지스터를 Linear Feedback Shift Register(줄여서 LFSR)라고 합니다. 일반적인 경우 선형 피드백 기능은 다음 공식으로 제공됩니다. 여기 ck= 1 경우 케이 th 비트는 피드백 기능에 사용되며, ck그렇지 않으면 = 0입니다. 기호 Å는 모듈로 2 추가(배타적 OR)를 나타냅니다.

예를 들어, 피드백 기능이 있는 LFSR을 고려하십시오(그림 참조).

레지스터의 초기 상태가 1111이면 후속 택트에서 다음과 같은 일련의 상태를 허용합니다. , 1110, 1111, 1111, 1111...

출력 시퀀스는 레지스터의 최하위(가장 오른쪽) 숫자로 구성됩니다. 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. 생성된 비트 시퀀스는 전적으로 레지스터의 초기 상태와 피드백 기능에 의해 결정된다는 것을 알 수 있습니다. 가능한 레지스터 상태의 수가 유한하기 때문에(2 엘) 그러면 조만간 키 시퀀스가 ​​반복되기 시작합니다. 키 시퀀스에서 반복되지 않는 부분의 최대 길이를 기간이라고 합니다. 티. 기간은 피드백 기능에 따라 다릅니다. 최대 가능 기간은 티최대=2 엘-1(레지스터는 0000...0을 제외한 모든 가능한 상태를 취함). 주기가 최대인 LFSR의 출력 시퀀스를 M-시퀀스.

LFSR이 최대 주기를 갖는 조건을 찾기 위해 피드백 함수는 특성 다항식과 일치합니다. 따라서 위에서 예로 든 레지스터는 다항식에 해당합니다. 이론적 분석에 따르면 LFSR은 다음과 같은 경우에만 최대 주기를 갖습니다. 피(엑스) 이다 원어. 다음은 실제 사용에 권장되는 몇 가지 기본 다항식입니다. 테이블은 변수의 정도를 보여줍니다 엑스다항식에서. 예를 들어 항목 (31, 3)은 다항식 과 일치합니다.

LFSR은 원래 하드웨어에서 일련의 디지털 회로로 구현되도록 설계되었습니다. LFSR의 소프트웨어 구현은 일반적으로 하드웨어 구현보다 느립니다. 성능을 높이려면 레지스터의 상태를 정수로 저장하는 것이 유리합니다. 엘- 레지스터의 이진수에 해당하는 개별 비트의 비트 번호. 그런 다음 비트 연산(시프트, 마스킹 등)을 사용하여 개별 비트에 액세스합니다.