[devel] Маленькая теоретическая задачка

[devel] Маленькая теоретическая задачка

[Paul Wolneykien]

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

  Только для условия задачи предположим также, что ваш знакомый хочет
вас обмануть: сделать вид что всё ещё бережно хранит файл, в то время
как давно его удалил (чтобы заполнить освободившееся место своими файлами).

  Каким образом можно, всё же, не дать ему обмануть вас? Вернее, сделать
это чрезвычайно трудным и невыгодным для него в смысле вычислительных
затрат и экономии дискового пространства?

---

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

  В том случае, если ваш знакомый не будет заранее знать, какую функцию
вы предложите ему вычислить, то ему придётся сохранить файл, по крайней
мере до тех пор, пока расчёты не будут произведены. Но для повторных
проверок нельзя использовать одну и ту же функцию: поняв, что результат
вычислений всегда один и тот же, ваш знакомый, поддавшись желанию
освободиться от ненужного ему файла, может его удалить. Значит функции
не должны повторяться.

  Добиться того, чтобы функции, передаваемые для вычисления контрольных
значений, действительно не повторялись, представляет определённую
трудность. Совершенно не похожие на первый взгляд функции могут
коррелировать известным образом. Если ваш знакомый хотя и потенциальный
обманщик, но хороший математик, то известная или легко обнаруживаемая
зависимость между функциями позволит ему получать новые контрольные
значения, на основании старых, что снова освобождает его от
необходимости хранить файл. Однако полностью избежать корреляции функций
не только сложно, но и невыгодно: в том случае если зависимость между
функциями полностью отсутствует, перед тем как удалить свою копию файла
придётся вычислить и сохранить у себя все возможные контрольные
значения. Такой подход, во первых, потребует дополнительных затрат
памяти, а во вторых, сделает количество возможных проверок конечным.
Значит функции, которые вы будете отправлять вашему знакомому для
проверки, должны коррелировать сложно обнаруживаемым, но известным для
вас способом.


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

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

  Павел.

Re: [devel] Маленькая теоретическая задачка

[Alexey I. Froloff]

[-- Attachment #1: Type: text/plain, Size: 243 bytes --]

On Sat, Sep 11, 2010 at 12:43:20AM +0400, Paul Wolneykien wrote:
>   Весь вопрос в том, что это за функции и каков способ их получения.
У Шнаера всё это описано.

-- 
Regards,    --
Sir Raorn.   --- http://thousandsofhate.blogspot.com/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] Маленькая теоретическая задачка

[Andrey Rahmatullin]

[-- Attachment #1: Type: text/plain, Size: 429 bytes --]

On Sat, Sep 11, 2010 at 01:04:31AM +0400, Alexey I. Froloff wrote:
> >   Весь вопрос в том, что это за функции и каков способ их получения.
> У Шнаера всё это описано.
+1

-- 
WBR, wRAR (ALT Linux Team)
Powered by the ALT Linux fortune(6):

> Зачем Вам геморрой с grub, если есть такой прекрасный инструмент как lilo?
Зачем Вам геморрой с lilo, если есть такой прекрасный инструмент как grub?
		-- wrar in community@

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [devel] Маленькая теоретическая задачка

[Paul Wolneykien]

11.09.2010 11:17, Andrey Rahmatullin пишет:
> On Sat, Sep 11, 2010 at 01:04:31AM +0400, Alexey I. Froloff wrote:
>>>   Весь вопрос в том, что это за функции и каков способ их получения.
>> У Шнаера всё это описано.
> +1

  Может быть Шнайер уже написал что-нибудь новенькое (кажется прошло 10
лет?), но в "Секретах и лжи" я не нашёл информации о том, как мне
получить то самое "индуктивное преобразование" -- простое для меня, но
сложное для остальных.
  Напомню, что для решения задачи по указанному мной сценарию, я должен
иметь возможность выполнить преобразование вида

  H_k -> ключ_индукции -> H_k+1 ,

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

  Или вы видите другое решение задачи?

Re: [devel] Маленькая теоретическая задачка

[Paul Wolneykien]

16.09.2010 23:37, Paul Wolneykien пишет:
> 11.09.2010 11:17, Andrey Rahmatullin пишет:
>> On Sat, Sep 11, 2010 at 01:04:31AM +0400, Alexey I. Froloff wrote:
>>>>   Весь вопрос в том, что это за функции и каков способ их получения.
>>> У Шнаера всё это описано.
>> +1
> 
>   Может быть Шнайер уже написал что-нибудь новенькое (кажется прошло 10
> лет?), но в "Секретах и лжи" я не нашёл информации о том, как мне
> получить то самое "индуктивное преобразование" -- простое для меня, но
> сложное для остальных.
>   Напомню, что для решения задачи по указанному мной сценарию, я должен
> иметь возможность выполнить преобразование вида
> 
>   H_k -> ключ_индукции -> H_k+1 ,
> 
>   где H_k -- контрольная сумма или хэш, который кроме этого можно
> получить, вычислив значение функции h_k(X), где X -- это набор моих
> данных, отданных на хранение.

  Дополнение. Раз уж я начал формализовать, нужно довести до конца. Итак.
  Функции h_1 ... h_N не коррелируют друг с другом: зная значение
функции h_k(X) нельзя (или очень трудно) вычислить значение функции
h_l(X), для всех l > k, не обладая ключом индукции.

> 
>   Или вы видите другое решение задачи?

Re: [devel] Маленькая теоретическая задачка

[Alexey I. Froloff]

[-- Attachment #1: Type: text/plain, Size: 411 bytes --]

On Thu, Sep 16, 2010 at 11:37:35PM +0400, Paul Wolneykien wrote:
> Может быть Шнайер уже написал что-нибудь новенькое
Не надо выдумывать сценарии.

> Напомню, что для решения задачи по указанному мной сценарию,
Не надо выдумывать сценарии самостоятельно.  Думайте над задачей,
а не над решением.

P.S. И при чём тут devel@?

-- 
Regards,    --
Sir Raorn.   --- http://thousandsofhate.blogspot.com/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] Маленькая теоретическая задачка

[Alexey I. Froloff]

[-- Attachment #1: Type: text/plain, Size: 333 bytes --]

On Thu, Sep 16, 2010 at 11:55:02PM +0400, Alexey I. Froloff wrote:
> > Может быть Шнайер уже написал что-нибудь новенькое
> Не надо выдумывать сценарии.
Я хотел сказать, что всё это есть в "стареньком", но пальцы за
мыслью вечером уже не успевают...

-- 
Regards,    --
Sir Raorn.   --- http://thousandsofhate.blogspot.com/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] Маленькая теоретическая задачка

[Paul Wolneykien]

16.09.2010 23:55, Alexey I. Froloff пишет:
> On Thu, Sep 16, 2010 at 11:37:35PM +0400, Paul Wolneykien wrote:
>> Может быть Шнайер уже написал что-нибудь новенькое
> Не надо выдумывать сценарии.
> 
>> Напомню, что для решения задачи по указанному мной сценарию,
> Не надо выдумывать сценарии самостоятельно.

  Ага. Именно поэтому я решил выдумывать их коллективно. Присоединяйся,
если хочешь.

>  Думайте над задачей,
> а не над решением.

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

> 
> P.S. И при чём тут devel@?

  М-м-м, а у нас есть math@, cs@ или lets-think@ ?

Re: [devel] Маленькая теоретическая задачка

[Alexey I. Froloff]

[-- Attachment #1: Type: text/plain, Size: 380 bytes --]

On Fri, Sep 17, 2010 at 12:25:09AM +0400, Paul Wolneykien wrote:
> Ага. Именно поэтому я решил выдумывать их коллективно. Присоединяйся,
> если хочешь.
Не хочу.  Читай Шнайера.

> > P.S. И при чём тут devel@?
> М-м-м, а у нас есть math@, cs@ или lets-think@ ?
Это не повод валить всё в devel@.

-- 
Regards,    --
Sir Raorn.   --- http://thousandsofhate.blogspot.com/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] Маленькая теоретическая задачка

[Andrey Rahmatullin]

[-- Attachment #1: Type: text/plain, Size: 430 bytes --]

On Thu, Sep 16, 2010 at 11:37:35PM +0400, Paul Wolneykien wrote:
>   Может быть Шнайер уже написал что-нибудь новенькое (кажется прошло 10
> лет?), но в "Секретах и лжи" 
"Секреты и ложь" не про криптографию.

-- 
WBR, wRAR (ALT Linux Team)
Powered by the ALT Linux fortune(6):

Ну я же тренируюсь в телепаты :) Чтобы человек как бы невнятно
вопрос ни задал, а ему бах - и ответ. И всем хорошо.
		-- lav in community@

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [devel] Маленькая теоретическая задачка

[Alexey Shabalin]

11.09.2010, в 0:43, Paul Wolneykien написал(а):


>
>
>  Весь вопрос в том, что это за функции и каков способ их получения.
>
Когда-то я писал курсовую и программу на Паскале "Исследование
корреляционного взаимодействия недвоичных М-последовательностей"
Была написана программа которая вычисляла все возможные
М-последовательности для 4,8,16,32,64 -ричных значений, а потом брала
каждую из них и сдвигала относительно другой, вычисляя корреляцию.
Сильно коррелирующие между собой последовательности отбрасывались, как
"плохие".
Запустив программу на i386, ждал больше пяти часов - не дождался, выключил.
На P-1 100MHz отработала за 30 минут :)