암호화를위한 행렬 곱셈 역함수

Question

암호화 alogritm을 함께 넣으려고하고 있지만 다음과 같은 문제에 갇혀 있고 이것조차 모르거나 그렇지 않다는 것을 알지 못합니다!

문제 :

I가 16 바이트가 매트릭스는 [16, 16] 행렬 승산하고, 그 결과는 16 바이트 행렬한다.

그러면 역행렬에 결과 행렬을 곱해야합니다. 여기서는 알고리즘 데이터 시트에 따라 원본 16 바이트 행렬을 가져와야한다고 가정합니다.

제 원래 매트릭스를 어떻게 다시 얻을 수 있는지 알려주시겠습니까?

미리 도움을 주셔서 감사합니다.

안부,

영어. Aws

Answer 1

내가 원하는 것을 달성하는 데는 여러 가지 방법이 있지만 몇 가지 세부 사항에 의존합니다.

매트릭스를 뒤집을 수있는 방법에는 여러 가지가 있습니다. (더 일반적으로는 선형 시스템을 풀기 위해). 몇 가지 예는 Gaussian elimination, Gauss-Jordan elimination 및 L/U decomposition입니다. 이들 중 하나를 사용하여 일반적인 선형 시스템을 해결할 수 있습니다 A x = bx; A의 역함수를 구하려면 행렬 X (I은 항등 행렬)에 대해 A X = I을 해결해야합니다.

가장 중요한 세부 정보는 "바이트를 곱하는 것"입니다. 곱셈은 ​​유한 필드의 일부 여야합니다. 아마도 GF(256) 일 수 있습니다. 그렇지 않으면 반전 할 수 없습니다. 특히, 이것은 "곱셈"이 프로세서와 네이티브 곱셈을 정규화하지 않는다는 것을 의미합니다. 대신, 약간의 부주의 또는 테이블 조회 (테이블은 상기 비트 피딩에 의해 미리 계산 됨)를 수행해야합니다. 또한, GF (256) "덧셈"과 "뺄셈"은 실제로 비트 xor입니다 (이는 서로 동일하다는 것을 의미합니다).

또 다른 사실 : 유한 필드를 사용하고 있기 때문에 피벗에 대해 걱정할 필요가 없다고 생각합니다. 설명 : 부동 소수점을 사용하는 경우, 선형 시스템 해석기는 부동 소수점 오차가 기하 급수적으로 누적되지 않도록하기 위해 기본 단계를 수행 할 순서를 선택해야합니다 (실제로 역행렬을 계산하지 않아도됩니다. 각 벡터에 대해 선형 시스템 해석을 사용하는 것이 유리함). 이러한 순서 선택은 "피보팅 (pivoting)"이라고하며, 선형 해석기에 대한 대부분의 참조는 많은주의를 기울입니다.

그러나 유한 필드 수학이 정확하기 때문에 이러한 종류의 불안정성에 대해 걱정할 필요가 없습니다. 솔버의 단계를 순차적으로 수행하고 정확한 역행렬을 구성 할 수 있습니다. 단 하나의 행렬 만 곱하면 정보가 손실되어 반전 될 수 없으며 사용 가능한 암호화 행렬이되지 않습니다.