Rot13 для номеров

Question

РЕДАКТИРОВАТЬ: Теперь сообщение о крупном движении в http://messymatters.com/sealedbids

Идея rot13 состоит в том, чтобы скрыть текст, например, чтобы предотвратить спойлеры. Он не предназначен для криптографической защиты, а просто для того, чтобы его могли прочитать только люди, которые уверены, что хотят его прочитать.

Я бы хотел сделать что-то похожее для чисел, для приложения с запечатанными заявками. Грубо говоря, я хочу послать кому-то свой номер и доверять ему, чтобы он выбрал свой собственный номер, не зависящий от моего, но тогда он сможет раскрыть мой (чисто клиентский), когда будет готов. Они не должны требовать дополнительной информации от меня или какой-либо третьей стороны.

(Добавлено: обратите внимание на предположение, что получателю доверяют, чтобы он не обманывал.)

Это не так просто, как rot13, потому что определенные числа, такие как 1 и 2, будут повторяться достаточно часто, чтобы вы могли помнить, что, скажем, 34.2 - это на самом деле 1.

Вот что я ищу конкретно:

Функция seal (), которая отображает действительное число в действительное число (или строку). Он должен , а не быть детерминированным - печать (7) не должна каждый раз отображаться на одно и то же. Но соответствующая функция unseal () должна быть детерминированной - unseal (seal (x)) должна равняться x для всех x. Я не хочу, чтобы печать или распечатка вызывали какие-либо веб-сервисы или даже получали системное время (потому что я не хочу использовать синхронизированные часы). (Добавлено: можно предположить, что все ставки будут меньше, чем какой-то максимум, известный всем, скажем, миллион.)

Проверка работоспособности:

> seal(7)
482.2382   # some random-seeming number or string.
> seal(7)
71.9217    # a completely different random-seeming number or string.
> unseal(seal(7))
7          # we always recover the original number by unsealing.

Answer 1

Вы можете упаковать свой номер как 4-байтовый с плавающей точкой вместе с другим случайным с плавающей точкой в ​​двойное число и отправить его. Клиент тогда просто должен забрать первые четыре байта. В питоне:

import struct, random
def seal(f):
   return struct.unpack("d",struct.pack("ff", f, random.random() ))[0]
def unseal(f):
   return struct.unpack("ff",struct.pack("d", f))[0]

>>> unseal( seal( 3))
3.0
>>> seal(3)
4.4533985422978706e-009
>>> seal(3)
9.0767582382536571e-010

Answer 2

Вот решение, вдохновленное ответом Сванте.

M = 9999  # Upper bound on bid.
seal(x) = M * randInt(9,99) + x
unseal(x) = x % M

Проверка работоспособности:

> seal(7)
716017
> seal(7)
518497
> unseal(seal(7))
7

Это требует настройки, чтобы разрешить отрицательные ставки:

M = 9999  # Numbers between -M/2 and M/2 can be sealed.
seal(x) = M * randInt(9,99) + x
unseal(x) = 
  m = x % M; 
  if m > M/2 return m - M else return m

Хорошая вещь в этом решении заключается в том, насколько легко получателю декодировать - просто мод на 9999 (а если это 5000 или больше, то это была отрицательная ставка, поэтому вычтите еще 9999). Также приятно, что скрытая ставка будет иметь длину не более 6 цифр. (Это достаточная безопасность для того, что я имею в виду - если ставки могут превышать 5 тыс. Долларов, я бы использовал более безопасный метод. Хотя, конечно, максимальная ставка в этом методе может быть установлена ​​настолько высокой, насколько вы захотите.)

Инструкция для мирян

Выберите число от 9 до 99 и умножьте его на 9999, затем добавьте ставку. Это даст 5 или 6-значный номер, который кодирует вашу ставку. Чтобы распечатать его, разделите на 9999, вычтите часть слева от десятичной точки, затем умножьте на 9999. (Это известно детям и математикам как «поиск остатка при делении на 9999» или «изменение на 9999» соответственно.)

Это работает для неотрицательных ставок менее 9999 (если этого недостаточно, используйте 99999 или столько цифр, сколько хотите). Если вы хотите разрешить отрицательные ставки, то магическое число 9999 должно быть в два раза больше максимально возможной ставки. А при декодировании, если результат больше половины 9999, то есть 5000 или более, вычтите 9999, чтобы получить фактическую (отрицательную) ставку.

Опять же, обратите внимание, что это относится к системе чести: технически ничто не мешает вам открыть номер другого человека, как только вы его увидите.

Answer 3

Если вы полагаетесь на честность пользователя и имеете дело только с целочисленными ставками, все, что вам нужно, это простая операция XOR со случайным числом, пример на C #:

static Random rng = new Random();

static string EncodeBid(int bid)
{
    int i = rng.Next();
    return String.Format("{0}:{1}", i, bid ^ i);
}

static int DecodeBid(string encodedBid)
{
    string[] d = encodedBid.Split(":".ToCharArray());
    return Convert.ToInt32(d[0]) ^ Convert.ToInt32(d[1]);
}

Использование:

int bid = 500;
string encodedBid = EncodeBid(bid); // encodedBid is something like 54017514:4017054 and will be different each time
int decodedBid = DecodeBid(encodedBid); // decodedBid is 500

Преобразование процесса декодирования в конструкцию на стороне клиента должно быть достаточно простым.

Answer 4

Есть ли максимальная ставка? Если это так, вы можете сделать это:

Пусть max-bid будет максимальной ставкой, а a-bid ставкой, которую вы хотите закодировать. Умножьте max-bid на довольно большое случайное число (если вы хотите использовать кодировку base64 на последнем шаге, max-rand должно быть (2^24/max-bid)-1, а min-rand, возможно, половина этого значения), затем добавьте a-bid. Закодируйте это, например, через base64.

Получатель затем просто должен декодировать и найти остаток по модулю max-bid.

Answer 5

То, что вы хотите сделать ( Схема фиксации ), невозможно сделать только на стороне клиента. Лучшее, что вы можете сделать, это зашифровать с помощью общего ключа.

Если клиенту не нужно ваше сотрудничество для раскрытия номера, он может просто изменить программу, чтобы узнать номер. Вы могли бы просто отправить его и не отображать.

Чтобы сделать это правильно, вы можете отправить безопасный хэш своей ставки + случайную соль. Это обязывает вас делать ставку. Другой клиент может подтвердить свою ставку таким же образом. Тогда вы каждый поделитесь своей ставкой и солью.

[править] Поскольку вы доверяете другому клиенту:

Sender:
Let M be your message
K = random 4-byte key
C1 = M xor hash(K) //hash optional: hides patterns in M xor K
//(you can repeat or truncate hash(K) as necessary to cover the message)
//(could also xor with output of a PRNG instead)
C2 = K append M //they need to know K to reveal the message
send C2 //(convert bytes to hex representation if needed)

Receiver:
receive C2
K = C2[:4]
C1 = C2[4:]
M = C1 xor hash(K)

Answer 6

Один простой способ - написать сообщение вроде:

"моя ставка: 14,23 $: aduigfurjwjnfdjfugfojdjkdskdfdhfddfuiodrnfnghfifyis"

Весь этот мусор генерируется случайным образом и каждый раз отличается.

Отправьте другому человеку хэш SHA256 сообщения. Пусть они отправят вам хэш своей ставки. Затем, когда у вас обоих есть хэши, отправьте полное сообщение и подтвердите, что их ставка соответствует хешу, который они вам дали.

Это дает довольно сильные гарантии, чем вам нужно - на самом деле они не могут отработать вашу ставку до того, как вы отправите им свое полное сообщение. Однако, как вы описываете, функции unseal () нет.

Эта простая схема имеет различные недостатки, которых не было бы у полной схемы с нулевым знанием. Например, если они подделывают вас, отправляя вам случайное число вместо хэша, то они могут определить вашу ставку, не раскрывая свою собственную. Но вы не просили пуленепробиваемые. Это предотвращает как случайный, так и (я думаю) не обнаруживаемый обман и использует только общедоступную утилиту командной строки, плюс генератор случайных чисел (игра в кости).

Если, как вы говорите, вы хотите, чтобы они могли восстановить вашу ставку без какого-либо дополнительного участия с вашей стороны, и вы готовы доверять им только после публикации ставки, просто зашифруйте ее с помощью любого старого симметричного шифра (gpg --symmetric, возможно) и ключ "rot13". Это предотвратит случайное мошенничество, но допустит не обнаруживаемый мошенничество.

Answer 7

Знаете ли вы, что вам нужен больший «запечатанный» набор чисел, чем ваш оригинал, если вы хотите, чтобы это работало?

Так что вам нужно как-то ограничить свои реальные цифры или хранить дополнительную информацию, которую вы не показываете.

Answer 8

Псевдокод:

закодировать:

value = 2000
key = random(0..255); // our key is only 2 bytes

// 'sealing it'
value = value XOR 2000;

// add key
sealed = (value << 16) | key

расшифровывает:

key = sealed & 0xFF
unsealed = key XOR (sealed >> 16)

Будет ли это работать?

Answer 9

Одна мысль, которая пришла мне в голову, состояла в том, чтобы основать ваш алгоритм на математике используется для безопасного обмена ключами.

Если вы хотите дать двум людям, Бобу и Алисе, по пол ключа каждый что, только комбинируя их, они смогут открывать любые замки с ключами, как ты это делаешь? Решение этого приходит из математики. Скажем, у вас есть две точки A (-2,2) и B (2,0) в системе координат x / y.

               |
       A       +
               |
               C
               |
---+---+---+---|---+---B---+---+---+---
               |
               +
               |
               +

Если вы проведете прямую линию между ними, она пересечет ось Y ровно в одной точке C (0,1). Если вам известна только одна из точек A или B, невозможно сказать, где она будет пересекаться. Таким образом, вы можете позволить точкам A и B быть общими ключами, которые при объединении покажут значение y точки пересечения (то есть 1 в этом примере), и это значение затем обычно используется как настоящий ключ к чему-то.

Для вашего приложения ставок вы можете разрешить seal () и unseal () поменять местами y значения между точками C и B (детерминированный), но время от времени точка A меняется.

Таким образом, печать (значение y точки B) даст совершенно разные результаты в зависимости от точки A, но unseal (печать (значение y точки B)) должно возвращать значение y B, которое вы и просили.

PS Не обязательно располагать A и B по разные стороны от оси y, но концептуально гораздо проще думать об этом (и я рекомендую также реализовать это).

С помощью этой прямой линии вы можете делиться ключами между несколькими людьми, так что только два они нужны, чтобы разблокировать что угодно. Можно использовать типы кривых, отличные от прямых, чтобы создать другое свойства совместного использования ключей (т. е. требуется 3 из 3 ключей и т. д.).

Answer 10

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

from random import randint

def seal(input):
    r = randint(0, 50)
    obfuscate = [str(r)] + [ str(ord(c) + r) for c in '%s' % input ]
    return ':'.join(obfuscate)

def unseal(input):
    tmp = input.split(':')
    r = int(tmp.pop(0))
    deobfuscate = [ chr(int(c) - r) for c in tmp ]
    return ''.join(deobfuscate)

# I suppose you would put your bid in here, for 100 dollars
tmp = seal('$100.00') # --> '1:37:50:49:49:47:49:49' (output varies)
print unseal(tmp) # --> '$100.00'

В какой-то момент (я думаю, что мы, возможно, уже прошли его) это становится глупым, и, поскольку это так просто, вам следует просто использовать простое шифрование, когда получатель сообщения всегда знает ключ - возможно, имя пользователя этого пользователя.