Эффективный алгоритм «Три корабля, одно сообщение»

Предпосылка состоит в том, что человек 1 хочет отправить секретное сообщение M (без обмена ключами) через океан человеку 2. Он решает отправить частичные сообщения через 3 корабля, например, если версии любых двух кораблей будут доставлены, человек 2 может построить полное сообщение. Исходное сообщение. Цель состоит в том, чтобы сделать каждое частичное сообщение (M1, M2, M3) неразборчивым само по себе. В случае поступления всех 3 сообщений избыточное сообщение может использоваться как ECC/четность.

Предположим, что сообщение состоит из последовательности 8-битных символов (m1,m2,m3...,mM). В наиболее эффективной кодировке len(M1+M2+M3) будет 1,5X len(M).

Неэффективное кодирование: M1 каждый символ состоит из старшего полубайта (UN) плюс нижний полубайт (LN), M2 состоит из UN минус LN, M3 представляет собой просто LN. M1 и M2 используют 5 бит на символ, M3 использует 4 бита на символ.

Примечание: назначение может быть повернуто таким образом, что M1 получит UN+LN,UN-LN,LN,... M2 получит сдвиг UN-LN,LN,UN+LN,.. M3 получит двойной сдвиг LN,UN+LN, UN-LN для того, чтобы:

1) Сделать сообщения одинаковой длины (по 3 символа) 2) Добавить дополнительную запутанность

Эта схема эффективна, но не эффективна. Любые предлагаемые улучшения или альтернативные методы?


cryptography algorithm information-theory redundancy
person DaveB    schedule 02.06.2015    source источник
comment
Какова точная модель безопасности здесь?   -  person David Eisenstat    schedule 02.06.2015
comment
И человек 1, и человек 2 знают алгоритм. Кроме того, в схеме чередования M1, M2 и M3 имеют 2-битный заголовок, указывающий, насколько велика ротация (при измерении эффективности служебные данные заголовка не учитываются). Теоретически M1 можно было бы отправить по мобильному телефону, M2 по электронной почте и M3 через курьерский CD-ROM). Идея заключается в том, что частичная информация является потенциально более эффективной формой защиты, чем, скажем, криптография с общим или закрытым ключом... и ее можно использовать снова и снова для нескольких сообщений.   -  person DaveB    schedule 02.06.2015
comment
что именно вы подразумеваете под наиболее эффективным? Если вы имеете в виду количество полученных пакетов (т. е. коэффициент потерь), то есть также схемы 2 из 4 и 2 из 8, которые не так уж плохи, но компромиссом является более высокая потребность в пропускной способности. Если вы имеете в виду эффективное использование полосы пропускания, вы можете потерять любой 1 пакет из N+1 пакетов, используя простые блоки XOR.   -  person rlb    schedule 02.06.2015
comment
Что касается современных технологий (скажем, IP-пакетов), мое определение эффективности расплывчато, потому что некоторые пакеты могут прийти. Применительно к трем различным сообщениям, M1, M2, M3, которые либо получены, либо не получены (корабль либо добирается, либо тонет в пути), len(M)*1,5 является оптимальным. (Это предполагает, что M уже сжато до максимальной энтропии).   -  person DaveB    schedule 02.06.2015

Ответы (1)


arrow_upward
0
arrow_downward

Предположим, что сообщение состоит из последовательности 8-битных символов (m1,m2,m3...,mM). В наиболее эффективной кодировке len(M1+M2+M3) будет 1,5X len(M).

Схема, отвечающая этому требованию:

  • M1 : старший полубайт (4 бита)
  • M2 : младший полубайт (4 бита)
  • M3 : XOR старшего полубайта и младшего полубайта (4 бита)

i.e:

    bit of original 8 byte:
M1: 7   6   5   4
M2: 3   2   1   0
M3: 7^3 6^2 5^1 4^0

В случае получения M1 и M2 у вас есть сообщение. В случае получения M1 и M3, M2 может быть восстановлен с помощью XOR M1 с M3. В случае получения M2 и M3, M1 может быть восстановлен с помощью XOR M2 с M3. В каждом случае 3-е значение может использоваться как проверка на четность.

Код можно еще больше запутать, перетасовав значение каждого бита в полубайте. Например, бит 0 может использовать описанный выше метод, но для бита 1 (полубайта) младший полубайт может быть в M1, значение XOR в M2 и т. д., т.е.:

    bit of original 8 byte:
M1: 7   6^2 1   4
M2: 3   6   5^1 0
M3: 7^3 2   5   4^0

Обратите внимание, что это обфускация, а не безопасность.

person samgak    schedule 02.06.2015