Рейтинг:0

Односторонняя функция text–текст

флаг jp

Мне нужен способ сопоставить некоторый печатный текст с другим печатным текстом. Например.:

Ян БойдККП Збас

Обратите внимание на некоторые важные требования:

  • верхний регистр в выводе в верхнем регистре
  • строчные буквы на входе строчные буквы на входе
  • пробелы (и все остальное за пределами A-Z0-9) оставляются в покое

Дополнительным требованием является наличие детерминированный, то есть один и тот же ввод всегда дает один и тот же вывод:

  • Ян БойдККП Xbas
  • Ян БойдККП Xbas
  • Ян БойдККП Xbas

Другое требование расширяет детерминизм, и я не знаю, как его назвать, кроме как сказать, что слова с общими префиксами должны иметь одинаковый вывод для одного и того же общего префикса:

  • яК
  • ЯКс
  • ЯнKcp
  • Ян Kcp
  • Ян БKcp X
  • Ян БоKcp Xb
  • Ян БойККП Хба
  • Ян БойдKcp Xbap

Мое решение

Я создал решение этих технических требований 15 лет назад; но я пытаюсь что-то пересмотреть "лучше".

Мое решение было "поточный шифр Цезаря с цепочкой".

Создайте простую замену Цезаря:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЫЭЮЯ
F H U D I R Y E K C Z N S A B G J P V O W T L M Q X

Но вместо простой замены:

  • Ян БойдФкс Hbqd

вместо этого я использовал цепочку:

Предыдущее состояние Текущая сумма символов (mod) Вывод следующего символа
----------------------------- ------------------ ---------- --------- ----- --------------------
0 Я (9) 9 К К
9 а (1) 10 в Кс
10 п (14) 24 п сп

24 Б (2) 26 Х Крп Х
26 о (15) 15 б Ксп Хб
15 лет (25) 14 a Kcp Xba
14 д (4) 18 м Kcp Xbap

Лучшее решение с хешированием?

Эти значения не то, что мне нужно (или хочу) "расшифровать", а использование шифра Цезаря предполагает возможность расшифровки (что, как мы все знаем, не так уж сложно).

Так что концептуально я действительно хочу "односторонняя функция": что-то, что:

  • преобразует ввод
  • к какому-то непредсказуемому результату
  • детерминистически

Я подумал: а что, если бы я использовал алгоритм хеширования, добавляя буквы по одной и получая текущую "государство", и преобразуйте этот частичный дайджест в символ (верхний/нижний регистр/цифру в соответствии с вводом):

   Строка FrobTheGrobber (ввод строки)
   {
      //доказательство концепции псевдокода, который обрабатывает только верхний регистр
      Хэш HashAlgorithm = новый SHA256();
      hash.AddBytes (SECRET_KEY);

      Строка рез = "";

      для Char ch на входе
      {
         хэш.Добавить(ch);
         int charCode = (hash.Hash[0] % 26) + 1; //используем первый байт по модулю 26, чтобы получить значение от 0 до 25
         res += Char(Ord('A') + charCode;
      }            
   }

Я знаю; ты ненавидишь требования.

Может ли кто-нибудь придумать что-нибудь лучше?

DannyNiu avatar
флаг vu
Ввести шифр Цезаря и заставить его работать как функция сжатия Дэвиса-Мейера?
DannyNiu avatar
флаг vu
Свойство префиксной идемпотентности затрудняет *не* обратное отображение.
fgrieu avatar
флаг ng
Подразумевает ли свойство префикса, что если «I» — «K», то «i» — «k», или может быть, что «i» — «z»? Что, если «Иан – Кср», то «Ян Ян» – «Кср Кср», или может быть, что «Ян Ян» – «Кср Зар»?
флаг jp
@fgrieu Для простоты это было * «без учета регистра» *, то есть «i» и «I» сопоставляются с «k» и «K». Полное решение также включает «0»-«9» в шифре Цезаря. Таким образом, такие вещи, как номера телефонов, сопоставляются с чем-то, что также выглядит как номер телефона (`905-867-5309` → `619-112-8408`). И я также мог бы отображать строчные буквы отдельно от прописных. В любом случае: не имеет значения. Если кто-то может придумать решение для `A`-`Z`, я могу расширить его на любые другие символы.
SAI Peregrinus avatar
флаг si
Как бы вы поступили с i и ι, которые сопоставляются с I? Просто игнорировать Турцию? Нечувствительность к регистру почти всегда УЖАСНАЯ идея, она всегда с потерями.
флаг jp
@SAIPeregrinus Этот вопрос не нуждается в этих деталях. Для целей этого вопроса вам нужно решить только обработку `A-Z`. Ответь на это, а я займусь остальным. Остальное тривиально для обработки и совершенно не имеет отношения к моему вопросу. Если это вам поможет: представьте, что исходная система использует 5-битную кодовую страницу, которая определяет только символы `A`-`Z`. Сказав все это, вы **точно** знаете, как я справлюсь с тестом на индейку, но это не часть моего вопроса, потому что это не важно для вопроса, и это не тот вопрос, который я задаю.
jjj avatar
флаг cn
jjj
С требованием префикса это не может быть односторонним, потому что можно легко восстановить его символ за символом.
Ievgeni avatar
флаг cn
Я не понимаю, какие требования безопасности?
Рейтинг:1
флаг ng

Проблема с первоначальным решением вопроса заключается в том, что таблица подстановки одинакова для каждого индекса и лучшей части ключа. Таким образом, это можно определить из примеров. Проблема с «лучшим» решением заключается в том, что зная начальное я шифрует в К, мы знаем инициал А шифрует в С, инициал Б шифрует в Д, и т.д..

Я предлагаю следующее, с не менее чем 256-битным хэшем $Ч$ такие как SHA-256 и ключ $К$:

  • установлен $ у = \ matthtt {\ текст {â0â}}$
  • для каждого персонажа $х$ зашифровать или расшифровать
    • позволять $б=0$
    • если $х$ это цифра, пусть $б=10$ и разреши $ c = \ matthtt {\ text {â0â}}$
    • если $х$ заглавная буква, пусть $б=26$ и разреши $ c = \ matthtt {\ text {A }} $
    • если $х$ это строчная буква, пусть $б=26$ и разреши $ c = \ matthtt {\ text {â a }} $
    • если $b\ne0$
      • установлен $K=H(K\mathbin\|\operatorname{uppercase}(y)\mathbin\|b)$
      • подготовить перестановку $р$ из $b$ элементы, отмеченные текущим значением $К$; и к этому:
        • установить целое число $ г = К $ (согласно соглашению с прямым порядком байтов)
        • за $я=0$ к $b-1$
          • установлен $j=r\bmod(i+1)$, тогда $r=\lfloor r/(i+1)\rfloor$
          • установлен $р[я]=я$
          • установлен $p[i]=p[j]$
          • установлен $p[j]=i$
      • при шифровании
        • установлен $у=х$
        • установлен $х=р[х-с]+с$
      • в противном случае
        • установлен $х=р^{-1}[х-с]+с$
        • установлен $у=х$
    • вывод $х$

И это дает результаты:

Введите текст Взбитый
я Б
Я БФ
Ян БФД
Ян БФД
Ян Б БФД К
Ян Бо Бфд Кф
Ян Бой Бфд Кфт
Ян Бойд БФД Кфтв
Ян Бойд БФД Кфтв
Ян Бойд 2 БФД Кфтв 2
Ян Бойд 20 БФД Кфтв 25
Ян Бойд 201 БФД Кфтв 257
Ян Бойд 2017 БФД Кфтв 2571

Попробуйте онлайн! в Питоне.

$K=H(K\mathbin\|\operatorname{uppercase}(y)\mathbin\|b)$ шаг подготавливает новый ключ, который зависит от предыдущего, от предыдущего символа (нормированного к верхнему регистру, потому что неясно, может ли капитализация иметь какое-либо влияние на следующие символы) и от того, является ли текущий символ цифрой или нет (поскольку правила позволяют, и мы хотим зависеть от того, насколько они позволяют). На каждом шагу $256-\log_2(26!)>167,6$ бит состояния остается неизвестным злоумышленнику даже при атаке с выбранным открытым текстом. Мы построили перестановку соответствующего размера в соответствии с текущим символом, в направлении, подходящем для шифрования или дешифрования.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.