О криптоанализе системы BBCRS на двоичных кодах Рида – Маллера

В работе рассматривается система система BBCRS – модификация криптосистемы Мак-Элиса, предложенная М. Балди и др. В модификации матрица $G_{pub}$ публичного ключа представляет собой произведение трех матриц: невырожденной $(k\times k)$-матрицы $S$, порождающей матрицы $G$ секретного $[n,k]_q$-кода $C_{sec}$ и невырожденной $(n\times n)$-матрицы $Q$ специального вида. Отличие системы BBCRS от системы, предложенной Р. Мак-Элисом, состоит в том, что подстановочная матрица, используемая в системе Мак-Элиса, заменена матрицей $Q$, представляющей сумму подстановочной матрицы $P$ и матрицы $R$ малого ранга $r(R)$. Позже В. Готье и др. построили атаку, позволяющую дешифровать сообщения в случае, когда $C_{sec}$ – обобщенный код Рида – Соломона (ОРС-код) и $r(R)=1$. Ключевыми этапами построенной атаки являются, во-первых, нахождение пересечения линейных оболочек $\mathcal{L}(G_{pub})=C_{pub}$ и $\mathcal{L}(G P)=C$, натянутых соответственно на строки матриц $G_{pub}$ и $G P$, а во-вторых, нахождение кода $С$ по подкоду $C_{pub}\cap C$. В настоящей работе строится атака в случае, когда $C_{sec}=\mathrm{RM}(r,m)$ – двоичный код Рида – Маллера порядка $r$ и длины $2^m$ при $r(R)=1$. В построенной в настоящей работе атаке этапы нахождения кодов $C_{pub}\cap C$ и $C$ полностью отличаются от соответствующих этапов для ОРС-кодов, а остальные шаги атаки адаптируют известные результаты криптоанализа системы BBCRS на ОРС-кодах.