Регистрация



Сейчас на сайте

Сейчас 11 гостей онлайн
Home Задачи
Информатика. Задачи
Задача i001-13 PDF Печать E-mail
Задача решена: 11 раз(-а) Попыток 81
Задача опубликована: 2013-03-09 10:00:00
Прислал: Dimon
Источник: 0
Вес: 100 Сложность 1 Класс 9-15 Баллы 100
Темы: шифровние комбинаторика
Комментариев:
Лучшее решение:
Решать: турнир закончен



Условие задачи

Переносный защищенный ПЭВМ/ноутбук производства корейского производителя защищённых ПК/КПК Getac

Защищенная операционная система

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

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


* * * * *


Дмитрий, предполагает, что все программы на языке SL-1 (Secure Language), которые должны работать с конкретным устройством SU-300, изначально будут зашифрованы уникальным для этого экземпляра устройства шифром простой замены и "прошиты" в это устройство.

Каждое устройство SU-300 будет снабжено уникальным электронным ключом, который содержит таблицу для расшифровки программ. Ну и понятно, что для того, чтобы такая программа могла исполняться, она должна быть сначала расшифрована этим электронным ключом.

При написании программ на SL-1 можно использовать все символы интернациональной чисти ASCII-таблицы, кроме управляющих символов и больших латинских букв. В таблице шифрования используются все допустимые символы, которые могут встретиться в программе.


* * * * *


При обсуждении аспектов коммерческой реализации идеи, встал вопрос, как много SU-300 можно будет произвести, чтобы каждое из них использовало уникальный шифр для исходных программ

Помогите Дмитрию с ответом.

* * * * *


Ответ введите в виде целого числа, без ненужных пробелов.


Дополнительная информация

 
Задача i002-13 PDF Печать E-mail
Задача решена: 4 раз(-а) Попыток 16
Задача опубликована: 2013-03-30 09:00:00
Прислал: Dimon
Источник: http://www.coursera.org
Вес: 1 Сложность 1 Класс 9-15 Баллы 250
Темы: вычисления дискретный логорифм
Комментариев:
Лучшее решение:
Решать: турнир закончен



Условие задачи

"А теперь посчитаем, уважаемые кроты!" Г.Х. Андерсен. Сказка "Дюймовочка"

"Встреча посередине"

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

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

* * * * *

Пусть g и h - некоторые элементы Z_{p}, такие, что h\ =\ g^x \(mod p), где 1\leq x \leq 2^{40}. Напомним также, что Z_p\ =\ \{0,1,2, ..., p-1\}

* * * * *

Наша цель - найти x. Более строго, на вход нашей программе поступают p,g,h, а на выходе мы получаем x.

* * * * *

Самый простой алгоритм - метод полного перебора. Можно попробовать перебрать 2^{40} значений x, и, в конце-концов, мы наткнемся на такое x, что h\ =\ g^x \(mod p). Однако, 2^{40} - слишком долгий перебор, поэтому попробуем его сократить до \sqrt{2^{40}}\ =\ 2^{20}. Используя атаку "встреча посередине" (meet in the middle attack).

* * * * *

Пусть B=2^{20}. Хотя x меньше, чем B^2, можно записать x=x_0\cdot B+x_1, где x_0 и x_1 целые числа из [0,B-1]. Тогда h\ =\ g^x\ = g^{x_{0}B+x_{1}}\ =\ \(g^B\)^{x_0}\cdot g^{x_1}\(mod p)

* * * * *

Перенесем g^{x_1} влево:

h\cdot \({g^{x_1}}\)^{-1}\ =\ \(g^B\)^{x_0}\(mod p).

Здесь \({g^{x_1}}\)^{-1} - число, обратное к g^{x_1} по \(mod p). Находится из соотношения g^{x_1}\cdot {g^{x_1}}^{-1}\ =\ 1\(mod p). (Поскольку в Z_p нет деления, то вместо того, чтобы разделить, мы должны умножать на обратные числа.) Для нахождения обратного числа можно применять расширенный алгоритм Евклида.

* * * * *

В полученном уравнении две переменные - x_0 и x_1. Поскольку они расположены в разных частях уравнения, можно применить атаку "встреча посередине":

  1. Сначала построим хеш-таблицу для h\cdot \(g^{x_1}\)^{-1} при всех значениях x_1\ =\ 0,1, ..., 2^{20}.
  2. Затем для каждого x_0\ =\ 0,1, ..., 2^{20} вычисляем \(g^B\)^{x_0} и проверяем, содержится ли оно в построенной ранее хеш-таблице. Если "да" - значит мы нашли решение \(x_0,x_1\) и то значение x, которое мы искали, есть x={x_0}\cdot B+x_1

* * * * *

Теперь у нас есть алгоритм. А задача, требующая решения, ниже:


p = 134078079299425970995740249982058461274793658205923933 \ 
    77723561443721764030073546976801874298166903427690031  \  
    858186486050853753882811946569946433649006084171

g = 11717829880366207009516117596335367088558084999998952205 \
    59997945906392949973658374667057217647146031292859482967 \
    5428279466566527115212748467589894601965568

h = 323947510405045044356526437872806578864909752095244 \
    952783479245297198197614329255807385693795855318053 \
    2878928001494706097394108577585732452307673444020333

Каждое из трех чисел содержат по 153 цифры. Требуется найти , такое x, что h\ =\ g^x \(mod p)

* * * * *

При вычислениях на языке Python рекомендуется использовать библиотеку gmpy2 или numbthy. При использовании языка C - библиотеку GMP.

* * * * *

Ответ введите в виде целого числа



 




Работает на Joomla!. Designed by: cheap gt cockpit best hosting provider uk Valid XHTML and CSS.