Шифрование цифрами: Шифрование цифрами. Шифр Цезаря — онлайн шифровка и расшифровка

Шифрование цифрами. Шифр Цезаря — онлайн шифровка и расшифровка

Моих воспоминаний с детских лет + воображения хватило ровно на один квест: десяток заданий, которые не дублируются.

Но детям забава понравилась, они просили еще квесты и пришлось лезть в инет.

В этой статье не будет описания сценария, легенд, оформления. Но будет 13 шифров, чтобы закодировать задания к квесту.

Шифр №1. Картинка

Рисунок или фото, которое напрямую указывает место, где спрятана следующая подсказка, или намек на него: веник +розетка = пылесос

Усложнение: сделайте паззл, разрезав фото на несколько частей.

Шифр 2. Чехарда.

Поменяйте в слове буквы местами: ДИВАН = НИДАВ

Шифр 3. Греческий алфавит.

Закодируйте послание буквами греческого алфавита, а детям выдайте ключ:

Шифр 4. Наоборот.

Пишете задание задом наперед:

• каждое слово:
  Етищи далк доп йонсос
• или все предложение, или даже абзац:
  етсем морком момас в — акзаксдоп яащюуделС. итуп монрев ан ыВ

Шифр 5. Зеркально.

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

Шифр 6. Ребус.

Слово кодируется в картинках:

Шифр 7. Следующая буква.

Пишем слово, заменяя все буквы в нем на следующие по алфавиту (тогда Я заменяется на А, по кругу). Или предыдущие, или следующие через 5 букв:).

ШКАФ = ЩЛБХ

Шифр 8. Классика в помощь.

Я брала стихотворение (и говорила детям, какое именно) и шифр из 2х цифр: № строки № буквы в строке.

Пример:

Пушкин «Зимний вечер»

Буря мглою небо кроет,

Вихри снежные крутя;

То, как зверь, она завоет,

То заплачет, как дитя,

То по кровле обветшалой

Вдруг соломой зашумит,

То, как путник запоздалый,

К нам в окошко застучит.

21 44 36 32 82 82 44 33 12 23 82 28

прочитали, где подсказка? 🙂

Шифр 9. Темница.

В решетку 3х3 вписываете буквы:

Тогда слово ОКНО шифруется так:

Шифр 10. Лабиринт.

Моим детям такой шифр пришелся по душе, он непохож на остальные, потому что не столько для мозгов, сколько на внимание.

Итак:

на длинную нитку/веревку цепляете буквы по порядку, как они идут в слове. Затем веревку растягиваете, закручиваете и всячески запутываете между опорами (деревьями, ножками итд). Пройдя по нитке, как по лабиринту, от 1й буквы до последней, дети узнают слово-подсказку.

А представьте, если обмотать таким образом одного из взрослых гостей!

Дети читают — Следующая подсказка на дяде Васе.

И бегут ощупывать дядю Васю. Эх, если он еще и щекотки боится, то весело будет всем!

Шифр 11. Невидимые чернила.

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

(есть и другие невидимые чернила.. молоко, лимон, еще что-то.. Но у меня в доме оказалась только свечка:))

Шифр 12. Белиберда.

Гласные буквы остаются без изменений, а согласные меняются, согласно ключу.

например:

ОВЕКЬ ЩОМОЗКО

читается как — ОЧЕНЬ ХОЛОДНО, если знать ключ:

Д Л Х Н Ч

З М Щ К В

Шифр 13. Окошки.

Детям понравилось неимоверно! Они потом этими окошками весь день друг другу послания шифровали.

Итак: на одном листе вырезаем окошки, столько, сколько букв в слове. Это трафарет, его прикладываем к чистому листу и «в окошках» пишем слово-подсказку. Затем трафарет убираем и на оставшемся чистом месте листа пишем много разных других ненужных букв. Прочитать шифр можно, если приложить трафарет с окошками.

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

Шифр 14. Карта, Билли!

Нарисуйте карту и отметьте (Х) место с кладом.

Когда я делала своим квест первый раз, то решила что карта — это им очень просто, поэтому нужно ее сделать загадочней (потом выяснилось, что детям хватило бы и просто карты, чтобы запутаться и бежать в противоположном направлении)…

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

Дети не сразу узнали местность, задавали мне наводящие вопросы..

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

«ПОКАЖИТЕ» «СКАЗКУ» «РЕПКА»

Это было следующее задание:). После него остались уморительные фото!

На 9ти летие сына не было времени выдумывать квест и я его купила на сайте MasterFuns .. На свой страх и риск, потому что описание там не очень.

Но нам с детьми понравилось, потому что:

1. недорого (аналог где-то 4х долларов за комплект)
2. быстро (заплатила — скачала-распечатала — на все про все минут 15-20)
3. заданий много, с запасом. Ихотя мне не все загадки понравились, но там было из чего выбрать, и можно было вписать свое задание
4. все оформлено в одном, монстерском, стиле и это придает празднику эффект. Помимо самих заданий к квесту, в комплект входят: открытка, флажки, украшения для стола, приглашения гостям. И все -в монстрах! 🙂
5. помимо 9ти летнего именинника и его друзей, у меня есть еще 5тилетняя дочка. Задания ей не по силам, но для нее и подружки тоже нашлось развлечение — 2 игры с монстрами, которые тоже были в наборе. Фух, в итоге — все довольны!

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

Шаги

Расшифровка шифров замещения

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

• Слова из одной буквы в русском языке — это местоимения и предлоги (я, в, у, о, а). Чтобы найти их, придется внимательно изучить текст. Угадывайте, проверяйте, закрепляйте или пробуйте новые варианты — иного метода разгадки шифра нет.
• Вы должны научиться читать шифр. Взламывать его — это не столь важно. Учитесь выхватывать шаблоны и правила, лежащие в основе шифра, и тогда его взлом не будет представлять для вас принципиальной сложности.

Инструкция

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

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

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

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

В более надежных шифрах замена букв производится по ключу. Например, ключом может стать многозначное число. Чтобы зашифровать таким образом текст, над ним много раз пишут число-ключ так, чтобы над каждой буквой оказалась цифра. После этого букву заменяют на другую, следующую после нее по через столько позиций, сколько обозначено цифрой. Алфавит при этом считается замкнутым в кольцо, то есть, например, второй буквой после «я» будет «б».

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

Глядя, какие варианты приводят к наиболее естественному на вид делению текста на слова, криптограф определяет, какими буквами кодируются пробелы, а значит — находит одну или несколько цифр ключа. Из этого уже можно начинать делать выводы, сколько раз ключ повторяется в тексте.

Подставляя на места пока еще неизвестных букв варианты из таблицы, криптограф определяет, в каких случаях в тексте появляются осмысленные слова и фрагменты.

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

Видео по теме

Источники:

• Владимир Жельников. Криптография от папируса до компьютера
  
• как заменить буквы на символы

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

Инструкция

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

Чтобы было легче заниматься , пользуйтесь ключами. Для дешифровки вам понадобится понятие, как длина ключа, определить которую вы сможете только методом подбора отдельных букв (см. шаг 1). После того как вы подберете длину вашего ключа, вы сможете сформировать группу символов, которая закодирована одной буквой. И так постепенно весь шифр откроется вам. Процесс этот достаточно трудоемкий и затратный по времени, поэтому запаситесь изрядной долей терпения.

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

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

Цифровые шифровки распознавайте при помощи математических методов. Один из популярных способов — использование теории вероятности. А в средние века с использованием математических символов производилась при помощи перестановки и использования магических квадратов. Это такие фигуры, в которые цифры вписываются в клетки последовательными натуральными числами. Начинаются, как правило, с 1. Секрет магического квадрата в том, что все цифры в нем в сумме каждого столбца или строки, или диагонали дают одно и то же число.

Учитывайте тот факт, что текст для дешифровки располагается в таком квадрате согласно нумерации клеток. Выпишите содержимое таблицы по и получите тот текст, который нужно расшифровать. А уже потом путем перестановок подберите необходимый вариант шифровки.

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

Когда-то мы со старшей Настей запоем играли в сыщиков и детективов, придумывали свои шифры, методы расследования. Потом это увлечение прошло и вот вернулось снова. У Насти появился жених Димка, который с упоением играет в разведчиков. Его увлечение разделила и моя дочь. Как известно, для того, чтобы передавать друг другу важные сведения, разведчикам нужен шифр. С помощью этих игр вы тоже узнаете, как зашифровать слово или даже целый текст!

Белые пятна

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

Например, вот во что превращается простое и понятное предложение «Встречаемся на берегу озера»
— «В стре чаем с Янабер егуоз ера»
.

Даже внимательный человек не сразу заметит подвох. Но опытный разведчик Димка говорит, что это самый простой вид шифровки.

Без гласных

Либо можно воспользоваться таким методом – писать текст без гласных букв.

Для примера привожу такое предложение: «Записка лежит в дупле дуба, который стоит на опушке леса»
. Шифрованный текст выглядит так: «Зпска лжт в дпл дб, ктр стт н пшке лс»
.

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

Читай наоборот

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

Вот, прочтите и расшифруйте: «Нелета минвь дуб, маноро тсоп иртомс»
.

Второй за первого

Либо каждую букву алфавита можно обозначить следующей за ней буквой. То есть вместо «а» мы пишем «б», вместо «б» напишем «в», вместо «в» — «г» и так далее.

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

Разгадайте, что за фразу мы для вас зашифровали: «Тьъйлб г тжсйбмж фиобуэ мждлп – по ожлпдеб ож тойнбжу щмарф»
.

Заместители

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

Вместо первой буквы алфавита мы пишем последнюю, вместо второй – предпоследнюю и так далее. То есть вместо А – Я, вместо Б – Ю, вместо В – Э…

Чтобы было легче расшифровать текст, нужно иметь под рукой алфавит и листочек с ручкой. Смотришь соответствие буквы и записываешь. Прикинуть на глазок и расшифровать ребенку будет трудно.

Таблицы

Можно зашифровать текст, предварительно записав его в таблицу. Только заранее нужно договориться, какой буквой вы будете отмечать пробелы между словами.

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

Давайте вместе зашифруем фразу с помощью таблицы: Ночью идем ловить карасей.

Пробел будем обозначать буквой «р», слова пишем сверху вниз. Таблица 3 на 3 (рисуем в клеточках обычного тетрадного листа).

Вот что у нас получается:

Н Ь И М О Т К А Й
О Ю Д Р В Ь А С Р
Ч Р Е Л И Р Р Е.

Решетка

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

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

Ключ в книге

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

Записки выглядели примерно так:
«324 с, 4 а, в, 7 сл.
150 с, 1 а, н, 11 сл….»

Первая цифра
обозначала номер страницы,
вторая
– номер абзаца,
третья буква
– как надо считать абзацы сверху (в) или снизу (н),
четвертая буква
– слово.

В моем примере нужные слова нужно искать:
Первое слово: на странице 324, в 4 абзаце сверху, седьмое слово.
Второе слово: на странице 150, в 1 абзаце снизу, одиннадцатое слово.

Процесс расшифровки небыстрый, зато никто из посторонних прочитать послание не сможет.

Воспользоваться старой и малоизвестной системой записи. Даже римские цифры не всегда бывает легко прочитать, особенно с первого взгляда и без справочника. Мало кто сможет «с лёта» определить, что в длинной строчке MMMCDLXXXIX скрывается число 3489.

С римской системой счисления знакомы многие, поэтому ее нельзя назвать надежной для шифрования. Гораздо лучше прибегнуть, например, к греческой системе, где цифры также обозначаются буквами, но букв используется намного больше. В надписи ОМГ, которую легко принять за распространенное в интернете выражение эмоций, может быть спрятано записанное по-гречески число 443. Буква «О микрон» соответствует числу 400, буквой «Мю» обозначается 40, ну а «Гамма» заменяет тройку.

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

Для таких случаев можно рекомендовать простой способ, которым в России в старые времена пользовались все те же бродячие торговцы — коробейники и офени. Для успешной торговли им было жизненно необходимо согласовывать между собой цены, но так, чтобы об этом не узнал никто посторонний. Поэтому коробейники и разработали множество хитроумных способов шифровки.

С цифрами они обходились следующим образом. Вначале нужно взять слово в котором есть десять различных букв, например «правосудие». Затем буквы нумеруются от единицы до нуля. «П» становится знаком для единицы, «в» — для четверки, и так далее. После этого любое число можно записывать буквами вместо цифр по обычной десятичной системе. Например, год 2011 записывается по системе офеней как «реепп». Попробуйте сами , спрятано в строчке «а,пвпоирс».

«Правосудие» — не единственное слово русского языка, подходящее для этого метода. «Трудолюбие» годится ничуть не хуже: в нем также десять неповторяющихся букв. Вы вполне можете и самостоятельно поискать другие возможные основы.

Не зря историю Египта считают одной из самых таинственных, а культуру одной из высокоразвитых. Древние египтяне, не в пример многим народам, не только умели возводить пирамиды и мумифицировать тела, но владели грамотой, вели счет, вычисляли небесные светила, фиксируя их координаты.

Десятичная система Египта

Современная десятичная появилась чуть более 2000 лет назад, однако египтяне владели ее аналогом еще во времена фараонов. Вместо громоздких индивидуальных буквенно-знаковых обозначений числа они использовали унифицированные знаки – графические изображения, цифры. Цифры они делили на единицы, десятки, сотни и т.д., обозначая каждую категорию специальным иероглифом.

Как такового правила цифр не было, то есть их могли в любом порядке, например, справа налево, слева направо. Иногда их даже составляли в вертикальную строку, при этом направление чтения цифрового ряда задавалось видом первой цифры – вытянутая (для вертикального чтения) или сплюснутая (для горизонтального).

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

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

Вид цифры

Цифровые иероглифы были геометричны и состояли только из прямых. Иероглифы выглядели достаточно просто, например цифра «1» у египтян обозначалась одной вертикальной полоской, «2» — двумя, «3» — тремя. А вот некоторые цифры, написанные , не поддаются современной логике, примером служит цифра «4», которая изображалась как одна горизонтальная полоска, а цифра «8» в виде двух горизонтальных полосок. Самыми сложными в написании считались цифры девять и шесть, они состояли из характерных черт под разным наклоном.

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

Одними из последних были расшифрованы и переведены иероглифы, обозначающих массу, совокупность. Сложность была объективной, ведь некоторые цифры изображались символично, к примеру, на папирусах человек, изображенный с поднятыми , обозначал миллион. Иероглиф с изображением жабы означал тысячу, а личинки — . Однако вся система написания цифр была систематизированной, очевидно – утверждают египтологи – что иероглифы упрощались. Вероятно, их написанию и обозначению обучали даже простой народ, потому как обнаруженные многочисленные торговые грамоты мелких лавочников были составлены грамотно.

Новости компании

Тайнопись, шифрование, секреты, спрятанные под покровом веков… Полагаете, что необходимость скрывать информацию появилась относительно недавно? Ученые считают иначе: найденные артефакты безоговорочно доказывают, что шифрование зародилось одновременно с появлением письменности.

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

1900 г. до нашей эры – первопроходцами шифрования были египтяне. Древняя египетская культура подарила нам не только величественного сфинкса и монументальные гробницы-пирамиды, но и первую тайнопись.

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

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

500 г. до нашей эры ознаменовался изобретением первого шифровального алгоритма. Жители иудейского царства придумали шифр ATBASH. Принцип этого шифра достаточно простой: одна буква алфавита заменяется другой ,следуя нехитрому алгоритму: искомая буква алфавита заменяется буквой с номером n — i + 1, где n — общее число букв в алфавите, а i – порядковый номер буквы. Слово «шифр», например, зашифрованное по принципу ATBASH будет выглядеть как «жцко».

Само слово «ATBASH» тоже построено по принципу замены букв. Его составляющие, буквы «алеф», «тав», «бет» и «шин», располагаются симметрично друг другу с разных концов еврейского алфавита.

Шифр ATBASH применялся и в Священном писании. Исследователей библейских текстов долгое время смущала фраза «…а царь Сессаха выпьет после них» в книге пророка Иеремии.  Упоминаний о загадочном царе или царстве не нашлось ни в хрониках, ни в книгах других пророков. И лишь дешифровав слово на языке оригинала при помощи шифра ATBASH, ученые выяснили, что имелся ввиду царь Вавилона.

500 лет до нашей эры —  где больше всего необходимо шифрование? Правильно, при военных действиях. А какой народ Древнего мира был известен непримиримой воинственностью? Правильно, спартанцы.

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

400 лет до нашей эры – не остались в стороне от шифрования и древние греки. Выдающийся полководец того времени, Эней Тактик, совершил революцию в шифровании: ему приписывают создание шифровального диска и линейки (диск и линейка Энея) и книжного шифра.

Диск Энея – это диск диаметром 10-15 с количеством отверстий, соответствующим количеству букв в алфавите. Для составления сообщения в дырку на диске, соответствующей определенной букве алфавита протягивалась нить. Дешифровка состояла в вытягивании нити, правда, сообщение следовало читать задом наперед.

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

Пионер тайнописи, Эней также был первым, кто подал идею использовать «книжный шифр». Он предложил делать в книгах или каких-либо бумажных документах незаметные проколы, которые вкупе составляли тайное послание.

200 лет до н. э. – древние эллины усовершенствовали технику шифрования, изобретя алгоритм, известный как Квадрат Полибия. В квадрат 5 на 5 записывались все буквы алфавита (ввиду того, что в греческом алфавите 24 буквы, одна ячейка оставалась пустой). Сообщение в зашифрованном виде передавалось факельщиками: подавалось два сигнала, соответственно обозначавшие положение буквы по горизонтали и вертикали.

100 лет до нашей эры – появление, наверное, самого знаменитого шифра Древнего мира – шифра Цезаря. Несмотря на свою популярность шифр может быть легко взломан, ведь алгоритм его незамысловат: каждая буква исходного текста заменяется символом, который располагается на X позиций левее или правее шифруемой буквы в алфавите. Предположим, что диапазон, на который следует сдвигаться 3, а направление движения вправо. Слово «шифр» в таком случае будет выглядеть как «ылчу».

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

Источники: http://www.wikipedia.org/, http://mail.ru/, http://kryptography.narod.ru/

Цифровые шифры | Тюрьма и жизнь за решеткой

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

АБВГ     ДЕЖЗ     ИКЛМ     НОПР     СТУФ     ХЦЧШ     ЩЫЮЯ
   1            2             3            4             5            6              7

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

53   14   42   33   42   13   41   72   31   44   42   24   72   51   32   

Алфавит может браться и не в обычном порядке, а с любой перестановкой букв.

2. Шифр может быть усложнен по следующей схеме:
 

Буквы составляются из двух цифр. Первая – ее место в группе, а вторая обозначает номер группы. Например, слово «опасность» в зашифрованном виде будет выглядеть так:

33 37 14 32 34 33 32 35 58

Для усложнения прочтения слово можно записать в одну строку:

333714323433323558

3. Сюда же можно отнести и цифровое письмо, где буквы разделяются на пять групп, каждая из которых снабжается двумя номерами.
 

 
Каждая буква изображается дробью таким образом, что числителем ее будет номер группы, а знаменателем – номер места в группе. Так как при этой схеме не употребляются цифры свыше шести, то цифры с семи до девяти можно использовать как пустые знаки.
Этим шифром слово «день» может быть записано следующим образом:

71 81 30 57
95 76 19 38

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

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

АБВГДЕЁЖЗИКЛМНОПРСТУФЧЦЧШЩЭЮЯ

Требуется зашифровать выражение:
«Встреча завтра».
Текст пишется для удобства шифрования вразрядку:

В С Т Р Е Ч А     З А В Т Р А
2  5 7 2  5  7 2     5  7 2 5 7  2

Под каждой буквой пишется по цифре до тех пор, пока не кончится фраза. Затем вместо каждой буквы текста пишется та буква алфавита, которая по счету оказывается первой вслед за таким количеством букв, какое показывает цифра, стоящая внизу, причем счет производится вправо. Так, под первой буквой «В» стоит цифра «2», поэтому вместо буквы «В» в шифровальном письме ставится третья буква алфавита «Д». Под второй буквой текста «С» стоит цифр «5», поэтому вместо нее ставится шестая после «С», т.е. буква «Ц».
В цифрованном виде письмо приобретет следующий вид:

ДЦШТКБВ НЖДЧЧВ

Для прочтения шифровки необходимо под каждую букву поставить ключевое, кодовое число. В нашем случае число 257. А в алфавите отсчитывать влево от данной буквы шифрованного письма столько букв, сколько показывает стоящая перед нею цифра.
Значит, вместо буквы «Д» вторая налево будет буква «В», а вместо «Ц» пятая, значит буква «С».

Д Ц Щ Т К Б В Н Ж Д Ч Ч В
2  5  7 2 5  7 2  5  7 2  5  7 2
В С Т Р Е Ч А З  А В Т  Р А

По материалам Л.А.Мильяненков
По ту сторону закона
энциклопедия преступного мира

Шифрование прогноза погоды во время войны

Ко Дню шифровальщика и 75-летию Победы в Великой Отечественной войне организаторы олимпиады «Готов к жизни в умном городе!» подготовили задачу про шифры.

Напоминаем, что до 12 мая проходит 2 этап пригласительного тура для учеников 2-8 классов школ Москвы, из которого и взята данная задача. Решение задачи про шифры и остальных вопросов олимпиады смотрите на видеоразборе 13 мая.

А с 14 по 28 мая пройдет основной тур олимпиады, на который приглашаются все желающие, вне зависимости от участия в пригласительном туре.

С приходом войны радикально поменялись требования к работе метеорологов. Точные и своевременные прогнозы погоды были крайне важны для всех уровней командования действующей армии и флота. Для организации работы в самом начале войны создаётся Главное управление гидрометеослужбы (15 июля 1941 года).

В ходе сбора данных с разнесённых по всей территории страны постов метеонаблюдения, а также рассылки метеосводок и долгосрочных прогнозов многочисленным адресатам через каналы связи проходил огромный объём информации. В отличие от мирного времени эту информацию уже нельзя было передавать в открытом виде. Исключения иногда делались только для штормовых предупреждений. Одной из ярких иллюстраций важности метеоданных для врага может служить история захвата в 1944 году одной из заполярных метеостанций немецким десантом, высадившимся с двух подводных лодок.  Его целью было получить таблицы кода «Полюс», применявшегося для шифрования данных метеонаблюдений (https://vk.com/kfront2019?w=wall-175797165_37). С другой стороны, криптографы советского военно-морского флота обеспечили сбор метеоданных и прогнозов из сетей связи сопредельных стран, что значительно повышало эффективность боевого применения авиации и кораблей. 

Рис 1. Фрагмент кода «Полюс»,  1944 год

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

Первым, но не единственным эшелоном защиты были так называемые переговорные таблицы, широко использовавшиеся в тактическом звене для скрытого управления войсками. Бланк одной из таких таблиц — «Переговорная гидрометеорологическая таблица (ПГМТ)», — применявшейся с 1942 года, приведён на фотографии архивного документа (рис. 2). В её клетках записаны буквы, цифры, а также некоторые часто используемые в сводках слова и словосочетания. 

Рис. 2. Таблица ПГМТ, 1943 год

Указать на нужную клетку, как и обычно, можно сообщив, в какой строке и каком столбце она расположена. Пустые клетки, являющиеся заголовками строк и столбцов, перед использованием заполнялись парами цифр. Эти пары, называемые ключом, рассылались всем абонентам сети заранее и потом регулярно изменялись. Пример расписания ключей приведён на следующей фотографии (рис.3).

Рис. 3. Расписание ключей ПГМТ, 1942 год.

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

Для зашифрования текста каждый его элемент (буква, слово) заменяется на четыре цифры, соответствующие заголовкам строки и столбца. Таким образом, длительной подготовки для использования ПГМТ от метеоролога не требовалось, а зашифрование/расшифрование сводки происходило достаточно быстро. 

Попробуйте расшифровать метеосводку, если известно, что использовался один из ключей на рис. 3.

5008 0338 5049 9080 3749 9049 1049 1038 8540 5849 1038 9080 1380 9090 9080 1340 9080 3740 1305 5880 5090 9075 1375 5040 1080 5840 8505 9008 8508 5840 0349 1308 8540 8580 9090 5040 1080 4040 1305 9075 1375 4040 1080 5040 8505 9008 1040 1080 5049 8508 

Вопросы

1. Какой фактор сильнее всего затруднял составление точных прогнозов погоды в период Великой Отечественной войны?

а) большое число пунктов сбора метеоданных на своей территории, предоставлявших по несколько сводок ежесуточно

б) задержки из-за времени, требовавшегося для расшифрования поступавших телеграмм с данными метеонаблюдений

в) отсутствие своих пунктов метеонаблюдений на зафронтовой территории 

г) шифрование противником своих рассылаемых прогнозов погоды 

2. Как вы думаете, передача по радио метеосводок, зашифрованных только с использованием ПГМТ, была

а. разрешена

б. запрещена

3. Какой ключ из расписания использовался?

а) с 1 по 10.10.1942 

б) с 11 по 20.20.1942 

в) с 21 по 31.10.1942 

4. Какая максимальная температура воздуха прогнозировалась в этой сводке?

Для иллюстраций использованы копии рассекреченных архивных документов Центрального архива МО РФ, размещённые на портале «Память народа». Задание составлено при участии НКО Фонд содействия развитию безопасных информационных технологий в рамках проекта «Криптографический фронт Великой Отечественной».

python — Шифрование Цезаря с пунктуацией, цифрами и прописными буквами ASCII?

Попытка заставить функцию шифра Цезаря включать прописные буквы ASCII, цифры и знаки препинания вместо только строчных. так что предложение вроде «hello1?» нажатая вперед одна клавиша превратится в «…

0

Ark Lomas

27 Мар 2021 в 15:58

1 ответ

Лучший ответ

Исправленный код:

from string import ascii_lowercase as letters
from string import punctuation
from string import digits

def encrypt(sentence, key):
    """
    key must be positive
    """
    print(f"Message: {sentence}")
    print(f"Key: {key}")
    enc = "".join(map(lambda x: (((2*letters)[letters.find(x) + key%len(letters)]) if x in letters else "" +
      ((2*punctuation)[punctuation.find(x) + key%len(punctuation)]) if x in punctuation else "" +
      ((2*digits)[digits.find(x) + key%len(digits)]) if x in digits else "" ), sentence))
    print(f"Encrypt: {enc}\n")
    return enc

try:
    line = input().lower()
    key = int(input())
    assert key > 0
except:
    key = 5


secret = encrypt(line, key)

Я проверил на своем конце, работает!

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

1

Vedant36
27 Мар 2021 в 16:48

Открытый и закрытый ключ шифрования

Ключ шифрования – это тайная информация (набор цифр и букв), которая используется алгоритмом для шифрования и расшифровки информации.

Надёжность ключа зависит от его длины в битах. В технологии SSL используют шифры 4096 бит для корневого сертификата и 128–256 бит для клиентских. Такая длина достаточна для безопасной передачи данных.

Протокол SSL использует асимметричное шифрование или шифрование с открытым ключом для установки соединения. Несмотря на название, здесь используются 2 ключа: открытый и закрытый. Оба формируются при запросе SSL-сертификата.

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

Закрытый (секретный ключ) известен только владельцу сайта. Используется для расшифровки данных, отправленных браузером.

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

Однако асимметричный алгоритм ресурсоемок, а скорость шифрования на 2-3 порядка ниже симметричного алгоритма. Поэтому в SSL-технологии шифрование с открытым ключом используется только для согласования секретного симметричного ключа. С его помощью устанавливается защищённое HTTPS-соединение – данные передаются быстро и безопасно.

Сразу использовать симметричное шифрование ненадежно. В этом алгоритме один и тот же ключ шифрует и расшифровывает информацию. Посетитель сайта и владелец сервера должны договориться о нем без свидетелей.

Передать по почте, телефону или смской не получится – перехватят или подслушают.

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

1. Чтобы аутентифицировать сервер, браузер посетителя проверяет, подписан ли SSL-сертификат сертификатом доверенного центра.
2. Чтобы договориться о симметричном ключе шифрования сервер и браузер используют асимметричное шифрование с открытым ключом.

Рассмотрим этот процесс на примере реальных ключей:

Боб отправляет Алисе замок, ключ от которого есть только у него.

Замок здесь – публичный ключ.

Алиса закрывает замком Боба ящик с секретом и посылает обратно.

Так же браузер шифрует сообщение с помощью публичного ключа и передаёт на сервер.

Открыть ящик не сможет никто: ни сама Алиса, ни сотрудники почты.

Мошенник точно так же не может расшифровать сообщение браузера без закрытого ключа.

Боб получает ящик, открывает своим единственным ключом и узнаёт секрет.

Сервер расшифровывает сообщение закрытым ключом, который есть только у него.

Как Алиса и Боб ведут тайную переписку, так браузер и сервер устанавливают защищённое HTTPS-соединение и обмениваются данными.

D-Link

Вопрос: Инструкция по настройке беспроводной сети

Ответ: 

Настройку рекомендуется производить через web-интерфейс. Для того чтобы в него попасть, откройте браузер (Internet Explorer или Mozilla Firefox) и введите в адресной строке 192.168.0.1

В появившемся окне введите:

Имя пользователя – admin

Пароль – admin

Нажмите «ВХОД».

Появится сообщение «Сейчас установлен пароль по умолчанию. В целях безопасности Вам рекомендуется сменить пароль.». Нажмите «ОК», установите новый пароль для доступа на web-интерфейс и нажмите «Сохранить».

Еще раз введите:

Имя пользователя – admin

Пароль – установленный Вами

Перейдите в меню Wi-Fi => Общие настройки и проверьте, чтобы стояла галочка «Включить беспроводное соединение».

Далее перейдите в меню Wi-Fi => Основные настройки.

Скрыть точку доступа– не ставьте галочку

SSID– пропишите имя беспроводной сети. Можно использовать латинские буквы и цифры

Страна – оставьте RUSSIAN FEDERATION

Канал – вместо AUTO установите любой канал с 1 по 11

Беспроводной режим – можете оставить без изменений или выбрать другой режим

Максимальное количество клиентов– можете установить максимальное количество беспроводных клиентов. Если установлен 0, количество клиентов неограниченно.

Нажмите «Изменить

После изменения настроек нажмите «Сохранить» в правом верхнем углу.

Далее перейдите в меню Wi-Fi => Настройки безопасности.

Сетевая аутентификация– рекомендуется устанавливать шифрование WPA-PSK/WPA2-PSKmixed

Ключ шифрования PSK– можете использовать ключ по умолчанию или установить свой (от 8 до 63 символов, можно использовать латинские буквы и цифры)

WPA-шифрование – выберите TKIP+AES

WPA период обновления ключа– оставьте без изменений

Нажмите «Изменить

После изменения настроек нажмите «Сохранить» в правом верхнем углу.

Настройка беспроводной сети завершена.

справочный запрос — Шифрование небольших сообщений

Вы хотите поговорить о шифровании с сохранением формата. Одним из основных мотивов FPE является возможность шифровать сообщения, которые находятся в коротком пространстве, с выводом, который находится в том же пространстве.

Идеальная модель шифрования на пространстве размером $ S $ (например, $ S = 10000 $ для четырехзначных PIN-кодов) состоит в том, что системы шифрования реализуют перестановку, выбранную случайным образом и единообразно из набора возможных перестановок $ S! $.Или, по крайней мере, что шифр неотличим от такой случайно выбранной перестановки.

Тогда модель крайней безопасности будет следующей: предположим, что злоумышленнику предоставлен черный ящик, который реализует алгоритмы шифрования (и дешифрования). Он может запросить шифрование или расшифровку почти полной кодовой книги, то есть запросов $ S-2 $. Злоумышленник может адаптивно выбирать содержимое каждого запроса. Таким образом, в этот момент злоумышленник может смоделировать полную функцию шифрования, за исключением двух входных значений: он знает два входа (назовем их $ p_0 $ и $ p_1 $) и два соответствующих выхода ($ s_0 $ и $ s_1 $). ), но он не знает, шифрует ли $ p_0 $ $ s_0 $ или $ s_1 $.Его цель — предсказать шифрование $ p_0 $ с вероятностью, значительно большей, чем чистая удача (то есть $ 1/2 $).

Обычно цитируемым решением для FPE является перетасовка Торпа. Это несбалансированный шифр Фейстеля с достаточным количеством раундов, чтобы сделать его безопасным. Хорошая часть этого состоит в том, что можно доказать безопасность , сохраняя при этом достаточно низкое количество раундов, чтобы быть практичным (скажем, 100 раундов или около того). Плохо то, что он не реализует экстремальную модель, описанную выше. Вы должны немного расслабить модель, потому что схема Фейстеля всегда реализует четную перестановку; поэтому, если вы знаете всю кодовую книгу, кроме шифрования $ p_0 $ и $ p_1 $, тогда вы можете решить, переходит ли $ p_0 $ в $ s_0 $ или $ s_1 $ со 100% успехом, потому что только один из двух вариантов приводит к ровной перестановке.Однако расслабление не имеет большого значения: если вы дадите злоумышленнику только $ S-3 $ запросов, тогда вы сможете получить наилучшее возможное в этих условиях (злоумышленник не может предсказать отображение трех оставшихся входов, за исключением того, что они будут должны соответствовать правилу «равной перестановки»).

Чтобы достичь «идеальной» модели с запросами $ S-2 $, вам нужно сделать более тяжелую вещь, например, создать полную перестановку в большом массиве (это, безусловно, выполнимо только с 10000 записей; для больших пространств решения с учетом памяти существуют, но цена процессора довольно высока).Для практического решения используйте перетасовку Thorp.

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

FPE используется для реализации других функций, например серийные номера с проверяемой достоверностью: вы определяете 8-значное число, в которое встроено 5-значное значение счетчика, и вам нужен инструмент, который может проверить, является ли данная последовательность из 8 цифр одной из 100000 последовательностей, которые вы выпустили; но вы не хотите, чтобы кто-либо другой мог генерировать случайные «действительные» последовательности с вероятностью успеха выше 1/1000. Решение состоит в том, чтобы закодировать 5-значный счетчик как 8 цифр, добавив три нуля, а затем зашифровать всю партию с помощью FPE.Чтобы проверить, расшифруйте и посмотрите, есть ли там три нуля.

Генерация ключей

— Влияют ли эти новые взгляды на простые числа на безопасность шифрования?

Нет, потому что это «открытие» ничего ценного не дает.

Они исследовали простые числа до одного миллиарда. В этом диапазоне примерно одно из восьми чисел, заканчивающихся на 1, 3, 7 или 9, являются простыми числами, а какие из них являются простыми числами, довольно непредсказуемо.

Если простое число p оканчивается цифрой 9, то числа p + 2, p + 4, p + 8, p + 10, p + 12 и т. Д.2 * 1/8 от — следующее простое число , потому что оно не может быть следующим простым числом, если равно p + 2 или p + 4, и так далее.

Так что их утверждение вполне может быть правдой, но это действительно тривиальный и очевидный результат, не имеющий никаких последствий. Они также опубликовали его на 16 дней раньше.

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

Теперь бросьте монету, затем несколько раз бросайте другую монету, пока эта монета не окажется такой же лицевой стороной вверх. 50% вероятность того, что это произойдет при первом броске, 25% вероятность того, что это произойдет при втором броске, 12,5%, что это произойдет при третьем броске и т. Д.

(Теперь то, что я сказал о простых числах, не совсем точно, потому что существует очевидная связь между последовательными числами, которые могут быть простыми. Если p простое, то p не делится на 3, что делает p + 6 также не делится на 3 и, следовательно, с большей вероятностью будет простым, в то время как p + 2 и p + 4 имеют более высокий шанс, чем случайное число, делиться на 3 и, следовательно, с меньшей вероятностью будут простыми числами.Аналогично для делимости на 7; если p простое, то p + 14, p + 28, p + 42 не делятся на 7 и, следовательно, с большей вероятностью будут простыми числами, в то время как другие числа — нет. Но это тоже давно известно

И этот бит должен успокоить тех, кто посчитал, что статья выходит за рамки того, что хотелось бы для случайных чисел. Вы можете найти все это, если будете искать «Харди, Литтлвуд», а корреляции между простотой ближайших чисел были подробно известны в середине 20 века).

PS. Вы абсолютно, абсолютно не используете соседние простые числа, например, для RSA, потому что произведение pq двух простых чисел можно тривиально разложить на множители, если разница между p и q не велика по сравнению с квадратным корнем из p или q.

Как действительно случайные числа укрепят ваше шифрование

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

Сюда входят такие вещи, как создание, хранение и уничтожение ключей. Специальная публикация NIST 800-57, часть 1, «Рекомендации по управлению ключами, часть 1: Общие», дает хороший обзор того, что необходимо для безопасного управления ключами. Этот документ состоит из 160 страниц, поэтому очевидно, что управление ключами — сложный и сложный процесс. И это слишком много, чтобы здесь рассказывать.

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

Безопасность шифрования

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

Вот почему стандарты, такие как SP 800-57, говорят нам, что 3072-битный ключ RSA, 256-битный ключ эллиптической кривой и 128-битный ключ AES обеспечивают примерно одинаковый уровень безопасности.RSA не менее безопасен, чем AES — просто нужен больший ключ, чтобы получить такой же уровень безопасности.

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

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

Это было основой для шифрования «экспортного уровня», которое требовалось в эпоху до доткомов. Программное обеспечение, использующее 128-битные ключи, могло быть экспортировано, но эти 128-битные ключи должны были иметь значительную неслучайную часть, оставляя только 40 из 128 битов, которые были неизвестны злоумышленнику. В то время такие более слабые ключи требовались государственными постановлениями, но если вы используете ключи, которые не генерируются случайным образом, вы можете использовать такое шифрование экспортного уровня, даже не подозревая об этом.

Случайность, а не энтропия

В Jacobellis v.Огайо , судья Поттер Стюарт отметил, что, хотя определение «непристойности» может быть трудным, он понял это, когда увидел это. Роберт Пирсиг сделал аналогичное заявление о «качестве» в своей книге Zen and the Art of Motorcycle Maintenance . Подобное расплывчатое мышление могло бы быть достаточно хорошим для юристов и философов, но нам действительно нужен более осторожный способ определения случайности в нашем контексте. Хорошая новость в том, что легко проверить, плох ли источник случайности. Плохая новость заключается в том, что гораздо сложнее проверить, является ли источник случайности хорошим.

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

Это связано с тем, что энтропия не имеет состояния — это статистика, которая вычисляется из последовательности выборок без какого-либо знания о том, что было до или что будет после конкретной выборки.Если наши выборки являются отдельными битами, то последовательность 0, 1, 0, 1, 0, 1,… будет иметь наивысший возможный теоретический уровень энтропии (один бит энтропии на символ), но явно не случайный.

Точно так же, если энтропия вычисляется на основе выборок, являющихся отдельными байтами, как это делает популярный инструмент ent, то последовательность 0x00, 0x01, 0x02,…, 0xff, повторяемая много раз, аналогичным образом будет иметь наивысший теоретический уровень энтропии (восемь битов энтропия на символ), но также явно не случайна.

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

Есть статистика, отличная от энтропии, которую мы можем использовать, чтобы убедиться, что данные из источника случайности будут давать результат, который противнику будет трудно угадать. NIST SP 800-90A Ред. 1, «Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов», определяет использование минимальной энтропии (иногда известной как «минимальная энтропия» или «минимальная энтропия»), статистики, которая тесно связана к энтропии, но лучше справляется с количественной оценкой того, насколько сложно злоумышленнику угадать случайное значение.

SP 800-90A даже определяет «энтропию» как то, что технически известно как минимальная энтропия, поэтому будьте особенно осторожны при чтении этого стандарта. А поскольку минимальная энтропия использует ту же модель без состояния, что и энтропия, она имеет те же ограничения — легко построить простые примеры данных с высокой минимальной энтропией, но явно не случайными.

К счастью, это ограничение хорошо понятно, и в недавней специальной публикации NIST (январь 2018 г.) 800-90B «Рекомендации по источникам энтропии, используемым для генерации случайных битов» перечислены тесты, которые можно использовать, чтобы убедиться, что ваш источник случайности не пытается надавить на вас, пользуясь причудами того, как определяется и вычисляется энтропия.

Насколько случайными должны быть ваши числа?

Итак, если вы будете следовать последним стандартам, вы сможете получить разумную уверенность в том, что любой источник случайности, который вы используете для генерации криптографических ключей, является достаточно случайным. Это не так просто и легко, как вы могли бы надеяться, но определенно намного лучше, чем просто полагаться на оценки энтропии. Шифрование экспортного уровня могло быть приемлемым еще в 90-е годы; это, вероятно, не то, что вы хотите использовать сегодня.Даже непреднамеренно.

Продолжайте учиться

Шифрование для детей!

Шифрование для детей!

Криптология для детей

Введение:

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

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

Как используется криптология?

Секретное письмо
использовались примерно столько же, сколько существовала письменность.Коды были использованы
на протяжении всей истории всякий раз, когда люди хотели, чтобы сообщения оставались конфиденциальными. Криптология используется уже давно
правительствами, военными, предприятиями и организациями для защиты своих
Сообщения. Сегодня шифрование используется для защиты хранилищ данных и транзакций.
между компьютерами. Визит
этот сайт, чтобы узнать больше: http://www.thunk.com/learn.html

В древности
когда сообщения переносились пешком на мили, короли и правители зашифровывали
письма, которые они отправят союзникам.
Это помогло защитить секретность сообщения на случай, если они были
украденный. В ранней американской истории
даже Джордж Вашингтон отправлял закодированные сообщения своим однополчанам. Точно так же члены Continental
Конгресс тоже закодировал их документы. Когда был изобретен телеграф, «азбуку Морзе» использовали для
отправлять понятные сообщения с помощью звуковых паттернов.

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

Ниже вы найдете
найти коллекцию ссылок на использование криптологии в истории.

Код Морзе:

о
Посетите это
веб-сайт для перевода (и прослушивания!) вашего собственного сообщения азбукой Морзе: http://www.soton.ac.uk/~scp93ch/morse/

Кодекс навахо
Говорящих в ВОВ:

о
Посетите этот сайт, чтобы узнать больше об этих
важные американцы и их роль в нашей победе во Второй мировой войне: http: // www.history.navy.mil/faqs/faq61-2.htm

ENIGMA во Второй мировой войне:

о
Учить больше
о кодовой машине ENIGMA, взломанной союзниками во Второй мировой войне http://www.odci.gov/cia/information/artifacts/enigma.htm

Секретные взломщики кода в истории:

о
Этот сайт http://codebreaker.dids.com/fhistory.htm
содержит много историй о роли шифрования в истории.

Вызов всех криптологов!

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

Сообщение для шифрования:

Красный
воздушный шар будет запущен завтра в полдень.
Предупредите все стороны!

Полезно
Ресурсы:

Следующие ссылки предоставят
вас с ассортиментом образцов методов шифрования. Обязательно изучите их все!

Цифры обозначают буквы

о
http://www.funology.com/braindrains/bd002.CFM

Криптографы

о
http://www.scouting.org.za/codes/sliding.html

Свиньи Шифры

о
http://www.scouting.org.za/codes/pigpen.html

Смешанный алфавит

о
http://www.funology.com/braindrains/bd001.cfm

Письма полиции алфавит

о
http: //www.happychild.org.uk/ifs/00001pla.htm

Буквы азбуки Морзе

о
http://www.happychild.org.uk/ifs/00003mrs.htm

FUN Cryptology Projects для
ВАМ попробовать:

Национальный
Запрос кода агентства безопасности:
Посетите этот сайт http://www.nsa.gov/programs/kids/standard/lab/elementary/index.shtml
чтобы начать свое путешествие в качестве секретного агента федерального правительства. Нажмите кнопку «Начать головоломку», чтобы
начинать.

Зеркало
Написание:
Если поднести что-нибудь к зеркалу
при письме написание выглядит перевернутым. Вы можете легко писать заметки и другие
вещи выглядят как зеркальное письмо. Возьмите лист тонкого белого или светлого цвета.
бумага. Темным маркером напишите что-нибудь на одной стороне. Убедитесь, что вы это написали
достаточно толстый и темный, чтобы просвечивать на другой стороне. Подбросить
по бумаге и проследите за тем, что написали. Вы проследите его в обратном направлении.Это
должно получиться так, как вы бы видели свое обычное письмо, если бы вы держали
это до зеркала. Для развлечения запишите разные слова или запишите на
кто-нибудь, затем переверните его и отправьте им.

Невидимый
Чернила:
Если вы пишете белым мелком на
белая бумажка, вроде там ничего нет. Но если ты тогда
закрасьте его, ваше невидимое письмо волшебным образом проявится. Писать слова,
фразы или даже записку для кого-то, а затем произвести на него впечатление, сделав это волшебным образом
появляться!

Криптограф
Колесо:
Можно сделать специальный криптограф
Колесо для решения криптографов (см. Картинку!) Сначала сделайте два круга из картона,
один немного меньше другого, и с помощью транспортира разметьте их на 26
штук около 13.По 8 градусов каждый. Напишите по одной букве алфавита в каждом
деление на каждое колесо. Затем соедините два колеса вместе с помощью шплинта.
так что вы можете вращать их независимо. Посетите этот сайт еще раз, чтобы
см. пример: http://www.scouting.org.za/codes/sliding.html

Американский
Язык жестов:
Используйте этот сайт, чтобы узнать больше о
подписывая алфавит. http://www.mikesart.net/clorisacom/signlanguage/?inputstring=hello
Вы можете научиться писать по буквам
слова.Введите слово в поле и нажмите «перевести», чтобы увидеть
как это выглядит на жестовом языке. Каждый палец представляет собой букву.

Метки:

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

Схема полного гомоморфного шифрования с ориентированным числом с плавающей запятой, сохраняющим конфиденциальность

Проблема сохранения конфиденциальности информации стала более заметной, особенно в отношении проблемы сохранения конфиденциальности в облачной среде.Гомоморфное шифрование может работать непосредственно с зашифрованным текстом; это шифрование обеспечивает новый метод сохранения конфиденциальности. Однако мы сталкиваемся с проблемой понимания того, как построить практическое полностью гомоморфное шифрование для нецелочисленных типов данных. В этой статье предлагается пересмотренная схема полностью гомоморфного шифрования с плавающей запятой (FFHE), которая достигает цели работы с числами с плавающей запятой без утечки конфиденциальности неавторизованным сторонам. Мы шифруем матрицу битов открытого текста как единый зашифрованный текст, чтобы уменьшить коэффициент расширения зашифрованного текста и уменьшить размер открытого ключа путем шифрования с использованием квадратичной формы в трех типах элементов открытого ключа и генераторах псевдослучайных чисел.Кроме того, мы делаем схему FFHE более применимой, обобщая гомоморфизм сложения и умножения чисел с плавающей запятой на аналитические функции с использованием формулы Тейлора. Мы доказываем, что схема FFHE для работы с зашифрованным текстом может ограничить дополнительную потерю точности. В частности, точность результата операции зашифрованного текста аналогична вычислению незашифрованного числа с плавающей запятой. По сравнению с другими схемами наша схема FFHE более практична для сохранения конфиденциальности в облачной среде с ее низким коэффициентом расширения зашифрованного текста и размером открытого ключа, поддержкой нескольких типов операций и высокой точностью.

1. Введение

В наш век больших данных объем данных, позволяющих идентифицировать людей, увеличивается. Люди наслаждаются удобством, создаваемым этими данными; в то же время утечка личных данных привлекла больше внимания, потому что эти данные легко доступны третьим сторонам, особенно в облачной среде, а также потому, что поставщик услуг может легко получить доступ к открытым текстам пользователей на облачном сервере. Кроме того, безопасность и конфиденциальность личных данных находятся под угрозой, поскольку мы внедряем услуги облачных вычислений; эта угроза считается самой большой проблемой в облачной среде [1].Чтобы избежать утечки данных, люди обычно применяют алгоритм шифрования, такой как AES, для шифрования этих данных и хранения их на облачном сервере. Однако AES не может поддерживать операции с шифрованными текстами непосредственно на облачном сервере. Когда людям необходимо использовать эти данные, они должны загружать зашифрованные тексты с сервера и расшифровывать их локально. Такие загрузки требуют большого расхода ресурсов. Используется только огромное пространство для хранения в облаке, в то время как доступность зашифрованных текстов теряется. Поэтому люди искали схему, которая могла бы использовать преимущества облака, включая огромное пространство для хранения данных и мощную вычислительную мощность, которая могла бы одновременно эффективно защитить конфиденциальность человека.Гомоморфное шифрование тесно связано с конфиденциальностью данных в облаке и является ключевой технологией для защиты конфиденциальности данных.

Гомоморфное шифрование позволяет третьим сторонам работать с зашифрованными значениями, не зная о содержимом. Идея гомоморфного шифрования заключается в следующем. Enc представляет алгоритм шифрования, а Dec представляет алгоритм дешифрования. Для функции, принимающей открытые тексты в качестве входных данных, существует функция, принимающая соответствующие зашифрованные тексты в качестве входных данных, где, в соответствии с указанным выше свойством гомоморфного шифрования, защита конфиденциальности пользователя в облачной среде представляется отличным методом.Мы можем воспользоваться преимуществами мощных вычислительных мощностей в облаке для работы с зашифрованными текстами, не раскрывая открытые тексты. Есть некоторые приложения, такие как CryptDB [7, 8] и другие зашифрованные базы данных [9, 10], которые применяют схему гомоморфного шифрования для защиты конфиденциальности данных.

Существующие схемы гомоморфного шифрования имеют некоторые ограничения. В большинстве практических систем применяется частично гомоморфная схема шифрования (некоторые ограниченные типы вычислений могут выполняться с зашифрованными текстами), такая как Пайе [11], а не полностью гомоморфная схема шифрования.Текущая полностью гомоморфная схема шифрования неэффективна. Также существует множество исследований по повышению эффективности полностью гомоморфных схем шифрования [3–5, 12, 13], но эти схемы не могут быть применены к практической системе. Более того, большинство современных схем гомоморфного шифрования работают только с целочисленным типом данных, в то время как большинство данных являются не только целыми числами. Например, в облачной службе электронного здравоохранения [14] модели принятия решений могут использоваться для автоматической проверки состояния здоровья пациента, а параметры модели принятия решений содержат действительные числа.Кроме того, нам часто требуется метод математического моделирования для анализа данных о состоянии здоровья пациента, который может использовать сложные функции, принимающие в качестве входных данных числа с плавающей запятой. Однако большинство существующих схем гомоморфного шифрования [2, 11, 15–18] сосредоточены только на операциях с целыми числами. Разработка схемы гомоморфного шифрования для вычисления чисел с плавающей запятой без ущерба для конфиденциальности данных, переданных на аутсорсинг, является сложной задачей.

В этой статье мы предлагаем полностью гомоморфную схему шифрования с плавающей запятой (FFHE) для преодоления вышеуказанных проблем.Схема основана на предложенной нами пересмотренной в некоторой степени гомоморфной схеме шифрования (RSHE), которая более эффективна, чем [3–5]. Хотя FFHE не подходит для практического применения в системе, мы повысили эффективность. Используя пять целых чисел для выражения числа с плавающей запятой [19], мы преобразуем операции над числом с плавающей запятой в целое число. FFHE может поддерживать операции сложения и умножения чисел с плавающей запятой. Затем мы доказываем, что операция с шифротекстами числа с плавающей запятой не увеличивает дополнительную потерю точности.Используя расчет приближения ряда Тейлора, наша схема может также вычислить результат функций анализа, таких как экспоненциальные и логистические функции, принимающие числа с плавающей запятой в качестве входных данных, не раскрывая открытых текстов.

Наш FFHE более эффективен, чем предыдущие работы. Он основан на оригинальном проекте Джентри и поддерживает более сложные функции с более разнообразными типами входных данных. Основные результаты этой статьи можно резюмировать следующим образом.

(i) Мы создаем более эффективную и в некоторой степени гомоморфную схему шифрования с меньшим размером открытого ключа и размером секретного ключа на основе [2], которая более эффективна, чем схема Корон [3–5].

(ii) Мы следуем плану Джентри и создаем полностью гомоморфную схему шифрования с плавающей запятой (FFHE), которая может поддерживать операции сложения и умножения над числами с плавающей запятой на основе предлагаемого нами пересмотренного отчасти гомоморфного шифрования (RSHE). По сравнению с операцией с открытыми текстами, сложение и умножение зашифрованных текстов не увеличивает дополнительную потерю точности.

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

Остальная часть этого документа организована следующим образом: соответствующая работа обсуждается в Разделе 2. В Разделе 3 мы описываем некоторые предварительные сведения, необходимые для понимания предлагаемой нами пересмотренной отчасти гомоморфной схемы шифрования и FFHE, а также некоторые предварительные знания о плавающих номера точек. В разделе 4 мы рассмотрим схему DGHV. Затем мы представляем пересмотренную несколько гомоморфную схему шифрования в разделе 5, а затем предлагаемый нами FFHE в разделе 6. В разделе 7 мы объясняем тип операций FFHE.Раздел 8 завершает эту статью.

2. Связанные работы

В этом разделе мы неформально рассмотрим предыдущие схемы гомоморфного шифрования. В 1978 году Ривест и др. предложил идею гомоморфизма конфиденциальности [20]: рабочие могут выполнять неявное сложение и умножение значений открытого текста, одновременно манипулируя исключительно зашифрованными данными. В последнее время гомоморфное шифрование привлекает значительное внимание исследователей. Существует множество исследований по гомоморфному шифрованию, включая несколько гомоморфную схему шифрования (важный компонент полностью гомоморфного шифрования, который допускает множество сложений и небольшое количество умножений на зашифрованные тексты) и частично гомоморфную схему шифрования.Например, RSA [15] — это мультипликативно гомоморфная схема шифрования, а криптосистема Пайе [11] — аддитивно гомоморфная схема шифрования.

Однако частично или частично гомоморфные схемы шифрования не могут удовлетворить требованиям обработки обширных данных о конфиденциальности. В своей революционной работе 2009 года Джентри построил первую схему шифрования, основанную на идеальных решетках, которые поддерживают как сложение, так и умножение зашифрованных текстов, то есть полностью гомоморфную схему шифрования [16], и подробно описал предложенную схему в своей докторской диссертации.Докторская диссертация [17], которая привела к исследованию полностью гомоморфного шифрования.

На основе исследования Джентри были построены три типа схем.

(1) Первоначальная схема Джентри была основана на идеальных решетках. Построение следует за последовательными шагами: во-первых, построить несколько гомоморфную схему, которая поддерживает ограниченное сложение и умножение на зашифрованных текстах. Этот шаг необходим, потому что зашифрованные тексты содержат некоторый шум, который становится больше при последовательном гомоморфном умножении, и только зашифрованные тексты, размер шума которых остается ниже определенного порога, могут быть дешифрованы правильно.Во-вторых, Джентри показывает, как сжать процедуру дешифрования, чтобы ее можно было выразить как полином низкой степени в битах зашифрованного текста и секретного ключа. Затем ключевая идея Джентри, называемая бутстрэппингом, состоит в гомоморфном вычислении этого полинома дешифрования при шифровании битов секретного ключа, что приводит к другому зашифрованному тексту (обновленному зашифрованному тексту), связанному с тем же открытым текстом с возможно уменьшенным шумом. Обновленный зашифрованный текст затем можно использовать в последующих гомоморфных операциях.При многократном обновлении зашифрованных текстов после каждой операции количество гомоморфных операций становится неограниченным, что приводит к полностью гомоморфной схеме шифрования. Джентри и Халеви реализовали схему Джентри [21] на основе алгоритмических оптимизаций, предложенных Смартом и др. [12].

(2) В 2012 г. Brakerski et al. предложила полностью гомоморфную схему шифрования (схема BGV) на основе задач обучения с ошибками (LWE) и кольцевого обучения с ошибками (RLWE) [18], которая была новым способом построения выровненной полностью гомоморфной схемы шифрования (способной оценивать произвольный полином -размер схем), без процедуры начальной загрузки Gentry.Они предложили методы переключения модулей и ключей для уменьшения шума и коэффициента расширения зашифрованного текста. Была описана реализация с эффективной гомоморфной оценкой полной схемы шифрования AES. В то же время эта ветка также привлекла значительное внимание, и они предложили переработанную схему на основе LWE [13, 22–25].

(3) На выставке Eurocrypt 2010 Дейк, Джентри, Халеви и Вайкунтанатан (схема DGHV) описали полностью гомоморфную схему шифрования целых чисел [2].Основная привлекательность схемы (по сравнению с исходной схемой Джентри) заключалась в ее концептуальной простоте; все операции производятся над целыми числами, а не над идеальными решетками. Однако открытый ключ был слишком большим для любой практической системы. По этой причине Coron et al. [3–5] предложили несколько методов оптимизации для уменьшения размера открытого ключа. Схема гомоморфного шифрования также может применяться в доказуемом владении данными [26–29].

Приведенные выше схемы относятся к операциям с целыми числами, в то время как исследований полностью гомоморфных схем шифрования для нецелых чисел мало.Вещественные числа — это наиболее распространенные числа, используемые при измерениях. В последнее время появились статьи, посвященные разработке полностью гомоморфной схемы шифрования действительных чисел. Сейко, Арита и Шота Накасато [30] предложили полностью гомоморфное шифрование для номеров точек, основанное на схеме FV [31], которая основана на проблеме LWE. Они создают первую схему гомоморфного шифрования, которая поддерживает операции с числами с фиксированной точкой. На основе этого они построили полностью гомоморфную схему шифрования, которая может гомоморфно вычислять сложение и умножение зашифрованных чисел с плавающей запятой.Cheon et al. [32] предложил схему гомоморфного шифрования с плавающей запятой, основанную на схеме BGV [18], которая была способна оценивать схемы произвольного полиномиального размера, аналогичные схеме BGV. Косташ [33] предложил арифметику с фиксированной точкой в ​​несколько гомоморфной схеме шифрования и исследовал ее применение в обработке гомоморфных изображений. Однако в этих статьях просто указана возможность построения схемы гомоморфного шифрования, поддерживающей операции над числами с плавающей запятой.Эти схемы не могут тайно вычислять сложные функции с числами с плавающей запятой в качестве входных данных. Кроме того, из-за низкой эффективности базовых схем по сравнению с целыми числами, предлагаемые ими схемы для нецелых чисел также требуют большого пространства ключей и пространства зашифрованного текста. Лю [34] выполнил аутсорсинговые вычисления для чисел с плавающей запятой. Они использовали криптосистему на основе Пайе для построения протокола работы над зашифрованными текстами. Однако Paillier — это только аддитивно гомоморфная схема, и они создают мультипликативно гомоморфную схему, устанавливая два сервера, что требует более высокой модели безопасности.

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

3. Предварительная

3.1. Обозначения

Для действительного числа мы обозначаем, используя,, и округляем вверх, вниз или до ближайшего целого числа. Для действительного и целого числа мы обозначаем сокращение по модулю с помощью или с. Позвольте быть реальным числом. Мы используем нотацию для представления значения с плавающей запятой (ближайшее число в системе с плавающей запятой). Наиболее полезными мерами точности являются абсолютная погрешность и относительная погрешность [19].

Параметры несколько гомоморфной схемы DGHV показаны в Разделе 4. Для данного параметра безопасности используются следующие параметры: — длина в битах открытых ключей. — битовая длина секретных ключей. битовая длина первого параметра шума. — количество открытых ключей. ’- битовая длина параметра вторичного шума.

Остальные параметры, используемые в предлагаемых нами схемах, будут описаны в разделах 5 и 6.

3.2. Число с плавающей запятой

Число с плавающей запятой — это формульное представление, которое аппроксимирует действительное число, чтобы поддерживать компромисс между диапазоном и точностью.Мы определяем формат с плавающей запятой, используемый в этой статье. Формат с плавающей запятой характеризуется пятью целыми числами [19]: где — знак. является основанием или основанием системы счисления ( b = 2 в этой статье). является целым числом такое, что называется показателем, где и — два экстремальных показателя, такие что. это точность (количество значащих цифр в значении) и удовлетворительное значение. Чтобы определить точность, мы определяем количество. Это наибольшее расстояние относительно единицы между действительным числом и ближайшим числом с плавающей запятой.Согласно приведенному выше определению относительной ошибки, мы представляем относительную ошибку как таковую. В соответствии с различными требованиями в практической системе мы можем настроить параметры в формате с плавающей запятой, который мы определили выше.

3.3. Анализ ошибок с плавающей запятой

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

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

Умножение двух действительных чисел может быть представлено так, что для каждого умножения относительная погрешность приблизительно удваивается. В частности, относительная ошибка будет увеличиваться при непрерывном умножении [19]. Предлагаемый ниже FFHE моделирует операции с открытым текстом в системе с плавающей запятой с помощью логической схемы. Мы доказываем, что относительная ошибка зашифрованного текста такая же, как у соответствующего открытого текста в нашем FFHE.

4. Несколько гомоморфная схема DGHV

В этом разделе мы напоминаем несколько гомоморфную схему шифрования над целыми числами Ван Дейка, Джентри, Халеви и Вайкунтанатана (DGHV) [2].Обозначения, используемые в схеме DGHV, такие же, как в разделе 3.1.

Для конкретного -битового нечетного целого p мы используем следующие битовые целые числа распределения:

DGHV.KenGen . Сгенерируйте -битовое случайное простое целое число, чтобы. Для образца. Обозначьте его так, чтобы он был самым большим. Перезагрузите, если нечетное и четное. Пусть и.

DGHV.Encrypt (pk, ) . Выберите случайное подмножество и случайное целое число r в и выведите зашифрованный текст:.

DGHV.Evaluate pk, , , , , . Учитывая схему с входными битами и зашифрованными текстами, примените шлюзы сложения и умножения к зашифрованным текстам, выполнив все операции сложения и умножения над целыми числами, и верните полученное целое число.

DGHV.Decrypt sk, . Выход .

Это завершает описание схемы, показанной в [2], схема является в некоторой степени гомоморфной схемой и семантически безопасна в предположении приближенного НОД, что доказано в [2].

Определение 1 (приблизительный НОД). Проблема заключается в следующем: дано случайное -битовое нечетное целое число p и дано много полиномиальных выборок из, при выводе p.

В соответствии с ограничениями параметров схемы предлагаются следующие параметры:,, и. Размер открытого ключа слишком велик для практической системы.

5. Пересмотренная в некоторой степени гомоморфная схема шифрования (RSHE)

В этом разделе мы предлагаем нашу пересмотренную несколько гомоморфную схему шифрования (RSHE) с меньшим размером открытого ключа и коэффициентом расширения зашифрованного текста.Как описано в разделе 4, размер открытого ключа DGHV слишком велик для практической системы. В литературе [3–5] предложено несколько вариантов схемы ДГХВ. Однако наш RSHE более эффективен, чем эти схемы, и подробное сравнение производительности нашего RSHE с этими схемами показано в разделе 5.2.

Как и в расширении в [3], мы расширяем схему DGHV для пакетной настройки. Вместо упаковки вектора открытого текста мы упаковали матрицу открытого текста с элементами в один зашифрованный текст, где.Вместо того, чтобы работать с целыми числами в форме, как в [21], мы сжимали все открытые ключи, используемые в RSHE, одинаковым образом, то есть, где и где. Затем в открытом ключе необходимо хранить только целые числа, чтобы сгенерировать целые числа, используемые для шифрования в [3]. Мы рассмотрели линейную комбинацию с коэффициентами in и линейную комбинацию in для дальнейшего уменьшения размера открытого ключа. Подробное описание RSHE следующее.

5.1. Описание

KeyGen : Выберите -битовые различные простые числа и обозначьте их произведение, то есть.Определите безошибочный элемент открытого ключа, где — сквозное целое число. Инициализировать два генератора псевдослучайных чисел f ₁ , f ₂ с двумя случайными начальными числами se ₁ , se ₂ (две функции генератора псевдослучайных чисел не зависят от друг с другом). Используйте и, чтобы сгенерировать набор целых чисел,,, позвольте вычислить первый набор открытых ключей: где и. Для всех и, вычислим. Для параметров шума,,,, вычислить второй набор открытых ключей: Для параметров шума вычислить третий набор открытых ключей: Мы называем расширенной функцией Кронекера следующим образом (определение функции Кронекера показано в [3]) : и используя технику сжатия, используемую для первого набора открытых ключей, мы также можем сжимать, разрешать и вычислять.

Пусть,.

Enc (pk, ) : создать случайную целочисленную матрицу,. Выведите зашифрованный текст:

Dec , : Выведите матрицу открытого текста:

Evaluate pk, C, ,…, : как в исходной схеме DGHV.

Добавить pk, , : Выход:

Mult pk, , : Выход:

5.2. Анализ параметров

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

: чтобы избежать атаки грубой силы на шум, и значение больше, чем в [5], чтобы быть защищенным от предлагаемой атаки. в [35].

: для предотвращения атак на основе решеток против приближенной задачи GCD [2].

: для поддержки гомоморфных операций для оценки сжатой схемы дешифрования [2].

: для правильной расшифровки зашифрованного текста (раздел 5.3).

Чтобы удовлетворить вышеуказанным ограничениям, мы можем взять,,,,,,,. Поскольку зашифрованные тексты сохраняются в форме матрицы, пусть степень раскрытия зашифрованного текста равна, размер нового секретного ключа такой же, как в [3]. Однако по сравнению с коэффициентом раскрытия зашифрованного текста в [2] наша схема была значительно улучшена.Новый открытый ключ для нашей пересмотренной в некоторой степени гомоморфной схемы имеет размер, а не как в [3] и как в [4]. Хотя размер открытого ключа в [5] равен, скорость расширения зашифрованного текста намного больше, чем в нашей статье. Мы предпочитаем немного больший размер открытого ключа для меньшей скорости расширения зашифрованного текста. По сравнению с открытым ключом, шифротексты требуют большего объема памяти. Кроме того, [6] объявляет размер открытого ключа своей схемы как; однако значение открытого ключа в схеме не соответствует ограничениям, предложенным в [2], и уязвимо для атак на основе решеток.Чтобы удовлетворить ограничения, размер открытого ключа равен, а фактический размер открытого ключа — не менее. Таким образом, предложенная нами схема лучше с точки зрения размера открытого ключа и скорости расширения зашифрованного текста.

Мы также выполняем анализ вычислительной сложности между этими схемами. Вычислительная сложность [2] равна, вычислительная сложность [4] составляет. Кроме того, вычислительная сложность [3, 5] — это все. Вычислительная сложность нашей схемы составляет. Мы не увеличили вычислительную сложность под предпосылкой уменьшения сложности пространства.

Подробное сравнение пространственной сложности и вычислительной сложности между вышеуказанными схемами показано в Таблице 1.

5.3. Корректность

Сначала определите разрешенные цепи следующим образом.

Определение 2 (допустимая цепь). Для любого и любого набора целочисленных входов, все меньше, чем по абсолютной величине, считается, что выход обобщенной схемы имеет абсолютное значение, не превышающее, где. Обозначим через множество разрешенных схем.

Согласно приведенной выше схеме зашифровать матрицу открытого текста m ₁ , ⋯, m _t , и сгенерировать вектор зашифрованного текста, где.Позвольте быть схемой с входами и выходом. Мы можем расшифровать правильно, если

Лемма 3. Наша несколько гомоморфная схема шифрования верна.

Доказательство. Шифрованный текст нашей схемы выглядит следующим образом: Для, у нас есть: Пусть будет логической схемой с вводом, и пусть будет связанной целочисленной схемой, в которой логические элементы заменены целочисленными операциями с зашифрованными текстами открытого текста для ввода. Для, у нас есть Согласно Определению 2, soThen, AndThen, наша схема верна для разрешенной цепи.

В схеме сложение приводит к линейному увеличению шума, а умножение приводит к экспоненциальному увеличению шума; следовательно, при увеличении шума преобладает умножение. Согласно Определению 2, выходы зашифрованного текста имеют шум, не превышающий; после умножения новый шум не превышает; пусть d будет степенью. Позвольте быть многомерным многочленом, вычисленным, и пусть будет нормой вектора коэффициентов. Затем, при условии, что тогда, как и в [5], мы называем многочлены разрешенными многочленами и обозначаем множество этих многочленов через.

5.4. Семантическая безопасность

Наша схема семантически безопасна при новом предположении, которое называется безошибочным — приближенным допущением GCD. Учитывая целые числа, мы определяем следующий оракул, который, заданный как входная матрица, выдает с помощью where. Обозначим через единственное целое число меньшее, чем такое, что для. Следовательно, выводит зашифрованный текст для открытого текста.

Определение 4 ( EF — AGCD ). Задача безошибочного приближенного НОД заключается в следующем.Выберите случайные -битовые целые числа продукта, случайные -битовые целые числа. Учитывая и доступ к оракулу, угадайте.

Таким образом, проблема принятия решения состоит в том, чтобы различить шифрование 0 и шифрование 1.

Теорема 5. Наша пересмотренная несколько гомоморфная схема шифрования семантически безопасна в предположении безошибочного приближенного НОД.

Доказательство. Злоумышленник принимает открытый ключ и выводит два сообщения и. Претендент возвращает шифрование случайного бита.Злоумышленник выводит предположение и преуспевает, если.
Мы вводим матричное представление зашифрованных текстов. С любым зашифрованным текстом мы связываем матрицу: в матрице зашифрованных текстов каждый зашифрованный текст может быть переписан в результате операции с матрицей, поскольку, где — матрица открытых текстов, и — два вектора, которые содержат случайный шум в третьем наборе общедоступных ключи. и являются случайными целочисленными матрицами. , содержат случайный шум во втором наборе открытых ключей и содержат случайный шум в первом наборе открытых ключей (с расширенными условиями функции Кронекера).В соответствии с ограничениями на параметры в разделе 5.1, пусть случайная величина однородна в Тогда статистическое расстояние между случайными величинами и не превышает. Следовательно, и.
Это завершает доказательство теоремы 5.

6. Схема полностью гомоморфного шифрования с плавающей точкой (FFHE)

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

6.1. Сжать схему расшифровки

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

Мы используем ту же технику, что и в [2], и обобщаем ее для пакетной настройки.Позвольте быть три новых параметра, конкретно,,,. Мы добавляем к открытому ключу набор рациональных чисел с битами точности после двоичной точки, так что для всех существует разреженное подмножество размера с. Мы также заменяем секретный ключ вектором индикатора подмножества. Формально, согласно RSHE в разделе 5.1, мы определяем FFHE следующим образом.

(1 ) KeyGen : Создать и как раньше. Пусть выбираются случайным образом -битовые векторы, каждый из которых имеет вес Хэмминга, для.Выбираем наугад целые числа для, выполняя условие, что для. Установите и. Каждое из них является положительным числом меньше двух, с битами точности после двоичной точки, и для некоторых проверяется.

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

Новый секретный ключ и новый открытый ключ.

(2 ) Enc (pk, m) : то же, что и в разделе 5.1.

(3 ) Expand ( , c) : процедура расширения зашифрованного текста принимает в качестве входных данных зашифрованный текст c и вычисляет расширенный зашифрованный текст: let с битами точности после двоичной точки для. Выведите развернутый зашифрованный текст.

(4 ) Dec ( , , , ⋯, ) : вывод:

Лемма 6. Схема после сжатия схемы дешифрования верна для набора схем, которые вычисляют разрешенные многочлены.

Доказательство. Согласно лемме 3, правильное расшифрованное сообщение дается, поэтому нам нужно показать, что тогда, чтобы удовлетворить ограничениям на параметры, у нас есть, итак, общее расстояние строго меньше 1/2. Это завершает доказательство.

6.2. Самозагрузка

Как и в [2], видно, что схема допускает загрузку.Из теоремы Джентри мы идентифицируем гомоморфные схемы шифрования для схем любой глубины.

Теорема 7. Пусть будет схема выше и пусть будет набор сжатых схем дешифрования. Потом, .

Для каждого открытого текста процедуры Expand естественно работают параллельно. Для, мы рассматриваем уравнение дешифрования: За исключением уравнения дешифрования, доказательство теоремы 7 идентично доказательству теоремы 3 в [2].

6.3. Анализ безопасности

Наша сжатая схема семантически безопасна с учетом жесткости предположения о сумме подмножества, которое упоминается в [2, 16].Мы используем анализ атаки из [4] проблемы суммы разреженных подмножеств. В нашей схеме злоумышленник должен решить следующее уравнение: где известны, а секретный ключ имеет малый вес Хэмминга. Мы предполагаем, что атакующий знает и поэтому.

Наша сжатая схема выполняет дополнительную пакетную операцию на основе [4]. Более того, процедуры Expand естественно работают параллельно с битами открытого текста, что означает, что шифротексты, зашифрованные разными секретными ключами, не будут мешать друг другу.Для каждого из них анализ атак аналогичен [4].

Согласно асимптотическому анализу в [4, 36], мы можем взять и избежать известных атак на проблему суммы разреженных подмножеств.

6.4. Вычисление с плавающей запятой

В соответствии с разделом 3.2 мы обозначаем число с плавающей запятой (пусть b = 2), которое может быть представлено в виде тройки и представляет собой постоянную точность. Чтобы безопасно хранить число с плавающей запятой, мы используем FFHE для его шифрования, поскольку, где — знаковый бит, — это -битное число.Зашифрованное число с плавающей запятой строится как. Затем мы определяем два типа схемных операций: «» как схему сложения и «» как схему умножения, которые принимают двоичные биты в качестве входных данных в операции открытого текста и принимают большие целочисленные зашифрованные тексты в качестве входных данных в операции зашифрованного текста.

Нельзя избежать сравнения размеров зашифрованных текстов при работе с зашифрованными текстами. Предположим, у нас есть два зашифрованных текста и, где и — целые числа. Определите бит как 1, если и как 0 в противном случае.Мы предлагаем протокол Greater-Than Bit (GTB) для вычисления шифрования бита с учетом только зашифрованных текстов и без знания секретного ключа.

и представляют собой целые числа со знаком. Они могут быть выражены как двоичные числа, и являются знаковыми битами соответственно. С помощью булевой схемы мы можем вычислить. Мы можем использовать дополнение до двух, чтобы добиться бинарного вычитания. Например, в частности, Следовательно, используя схему сложения, мы определяем «» как схему вычитания, как указано выше (нам не нужна операция по модулю в операции вычитания зашифрованных текстов).

Протокол Greater-Than Bit . Мы используем схему вычитания для реализации предлагаемого нами протокола GTB. Учитывая два зашифрованных текста и, протокол GTB должен отображать или. Общие шаги GTB показаны ниже.

Шаг 1. Мы выполняем схему вычитания для вычисления зашифрованных текстов. Вход нашей схемы FFHE — двоичный бит; следовательно, зашифрованный текст является битом знака.

Шаг 2. Нам нужно проверить, совпадают ли признаки и.- это зашифрованный текст для 1, когда знаки и одинаковы, и это зашифрованный текст для 0, когда знаки и различны.

Шаг 3. Мы определяем протокол GTB как. Gtb — это зашифрованный текст для 0, когда, и зашифрованный текст для 1, когда.

Протокол эквивалентных битов . Дополнительно необходимо проверить, эквивалентны ли два числа. Поэтому мы предлагаем протокол Equivalent-Bit (EB). Учитывая два зашифрованных текста и, протокол EB должен показать, есть ли.Общие шаги протокола EB показаны ниже.

Шаг 1. Выполняем протокол GTB для проверки или.

Шаг 2. Мы определяем протокол EB как. Обратите внимание, что если, то. Иначе, .

Протокол левого переключения передач . При сложении чисел с плавающей запятой необходимо унифицировать показатели этих чисел с плавающей запятой. Поэтому мы предлагаем протокол Left Shift (LS) для корректировки мантиссы числа с плавающей запятой. Зная зашифрованный текст мантиссы и два зашифрованных текста экспонент, вычисляем, где.Общие шаги протокола LS показаны ниже.

Шаг 1. For in (- экстремальный показатель, описанный в разделе 3.2), Return.

Мы определяем протокол LS как. Мы также предлагаем протокол сложения чисел с плавающей запятой (FAdd) и протокол умножения чисел с плавающей запятой (FMult) для вычисления сложения и умножения зашифрованных текстов чисел с плавающей запятой. Предположим, у нас есть два числа с плавающей запятой,. Шифрованные тексты — это и соответственно.Общие шаги протокола FAdd и протокола FMult показаны ниже.

Протокол добавления чисел с плавающей запятой

Шаг 1. Нам нужно проверить соответствие знаков и. — это зашифрованный текст для 1, когда, и — это зашифрованный текст для 0, когда. Предположим, что бит знака равен.

Шаг 2. Если знак совпадает со знаком большего между и, в частности, знаковый бит имеет следующий вид:

Шаг 3. Вычисляем знак сложения и.

Шаг 4. Когда значение имеет следующий вид: Следовательно, мы вычисляем окончательное значение сложения и. Оно показывает, что это k + l двоичных разряда, а точность результата равна к + л .

Шаг 5. Если, он показывает, что показатель степени равен. Если, это показывает, что показатель степени равен. Построение выглядит следующим образом: Мы вычисляем показатель степени сложения x и y .

Шаг 6. Наконец, нам нужно сохранить значащие биты результата. Следовательно, это двоичные биты. Результат сложения можно представить как, в частности,.

Как и выше, точность остается. Сложение с плавающей запятой не добавляет дополнительной относительной ошибки. Для последующих операций точность остается неизменной, а относительная погрешность — как в разделе 3.2.

Протокол умножения чисел с плавающей запятой

Шаг 1. Сначала мы вычисляем знак умножения и.

Шаг 2. Затем вычисляем показатель степени.

Шаг 3. Наконец, мы вычисляем мантиссу. Она показывает, что это 2 k двоичных разряда, а точность результата составляет 2 k .

Шаг 4. После этого нам нужно сохранить значащие биты результата. Следовательно, это двоичные биты. Результат умножения можно представить как, в частности,

. Как и выше, точность остается неизменной. Согласно разделу 3.2, верхняя граница относительной погрешности умножения будет вдвое больше исходной,. То есть после n-уровневой операции умножения верхняя граница будет такой же, как операция с числами с плавающей запятой в открытом тексте.

Схема FFHE полностью имитирует операцию с плавающей запятой в открытом тексте в форме схемы, так что относительная ошибка результата операции в зашифрованном тексте не увеличивается по сравнению с результатом в открытом тексте.

7. Типы вычислений Обобщение FFHE

В разделах 5 и 6 мы предложили нашу пересмотренную несколько гомоморфную схему шифрования (RSHE) и нашу полностью гомоморфную схему шифрования с плавающей запятой (FFHE).Как мы видим, FFHE описывает только пять основных протоколов для выполнения различных операций с числами с плавающей запятой, включая сложение и умножение, и большинство современных схем гомоморфного шифрования также включают только сложение и умножение [2–5, 18]. Однако сложные функции, принимающие числа с плавающей запятой в качестве входных данных, в действительности более распространены, и нам также необходимо защитить конфиденциальность ввода и вывода для этих сложных функций. Например, в облачной службе электронного здравоохранения [14] нам часто требуется метод математического моделирования для анализа данных о состоянии здоровья пациентов, который может использовать некоторые сложные функции, принимающие числа с плавающей запятой в качестве входных данных.В этом разделе вспомогательные типы вычислений FFHE обобщены от сложения и умножения до аналитических функций, например, обратной функции, экспоненциальной функции и логарифмической функции. Оценка взаимной функции также обеспечивает новый идеал для вычислительного разделения без утечки конфиденциальности.

Определение 8 (гомоморфизм функций). Позвольте быть аналитической функцией, гомоморфной схемой шифрования, которая удовлетворяет гомоморфизму функций ifwhere — соответствующая функция, работающая над шифротекстами.

Используя ряды Тейлора, наш FFHE может гомоморфно оценивать аналитические функции, принимая в качестве входных данных числа с плавающей запятой. Согласно разделу 6.3, FFHE реализует протоколы оценки сложения и умножения для чисел с плавающей запятой, а полиномы состоят из сложения и умножения. Следовательно, FFHE может гомоморфно вычислять полиномиальную функцию. Ряд Тейлора устанавливает связь между аналитической функцией и полиномиальной функцией. Определение ряда Тейлора следующее.

Определение 9 (серия Тейлора). Ряд Тейлора действительной или комплекснозначной функции, бесконечно дифференцируемой по действительному или комплексному числу a является степенным рядом: который может быть записан в более компактной сигма-нотации, где где обозначает факториал и обозначает -й производная оценивается в точке. Производная нулевого порядка определяется как и и 0! оба определены как 1. Когда a = 0, ряд также называется рядом Маклорена.

Используя ряд Тейлора, аналитические функции можно переписать как комбинацию сложений и умножений, которые обеспечивают метод оценки аналитических функций без раскрытия конфиденциальности. Однако должно быть выполнено основное условие, заключающееся в том, что независимая переменная должна находиться в сходящейся области. Мы цитируем обратную величину и экспоненту, которые можно переписать как ряд Тейлора в приведенном ниже примере. Позвольте — степень многочлена. Чем больше n, тем меньше ошибка.Пусть ниже a = 0.

Пример 10. обратная величина

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

Ряд Тейлора:

Конвергентная область:, где.

Ошибка:

Точность чисел с плавающей запятой в нашем FFHE составляет. Если полином Тейлора не может снизить точность. В частности, степень должна удовлетворять. Приблизительное вычисление обратной величины с рядом Тейлора обеспечивает метод вычисления деления.

Пример 11. показатель степени

Описание: вычислить показатель степени, то есть.

Серия Тейлора:

Конвергентная область:, где,

Ошибка:

Пусть тогда и ошибка, пусть, ошибка не будет превышать.

Другие аналитические функции, такие как тригонометрические функции, логарифмические функции и варианты этих функций, также могут быть переписаны как ряды Тейлора; однако независимая переменная должна находиться в конвергентной области.Ниже мы проиллюстрируем, как рассчитывать за пределами конвергентной области.

Как отмечалось выше, при вычислении обратной величины конвергентная область равна. Предполагать ; мы можем преобразовать формулу как Let, а показатель степени равен. Затем его можно переписать как ряд Тейлора, как указано выше, в сходящейся области. Произведение ряда Тейлора и является приблизительным значением с потерей точности в битах. Увеличивая значение и, можно соответствующим образом повысить точность.Если, приблизительное значение можно рассчитать таким же образом. Вычисление других аналитических функций с независимой переменной, находящейся вне конвергентной области, может быть выполнено аналогичным методом. Расширение или сокращение диапазона независимых переменных — эффективный метод удовлетворения условия конвергентной области. Из-за разнообразия и ограничений по длине статьи они здесь не рассматриваются.

Точность можно повысить за счет увеличения, но это приводит к более высокой сложности вычислений.В соответствии с фактическим спросом мы можем определить размер n, чтобы достичь баланса между точностью и сложностью вычислений.

Схема FFHE — это полностью гомоморфная схема шифрования, которая поддерживает операции аналитических функций на основе чисел с плавающей запятой. В таблице 2 сравнивается наша схема FFHE с [2–4, 6].

8.Заключение

В этой статье мы следовали плану Джентри, чтобы построить пересмотренную полностью гомоморфную схему шифрования, которая поддерживает многие аналитические операции над числами с плавающей запятой, а не только операции сложения и умножения над целыми числами. Упаковывая матрицу битов открытого текста в единый зашифрованный текст, мы уменьшаем скорость расширения зашифрованного текста до. В то же время, используя квадратичную форму вместо линейной в трех типах открытого ключа и множественном генераторе псевдослучайных чисел, мы уменьшаем размер открытого ключа до.Мы построили пересмотренную полностью гомоморфную схему шифрования с плавающей запятой (FFHE). Схема остается семантически безопасной при решении проблемы безошибочного приближенного НОД и проблемы суммы разреженных подмножеств (SSSP). В FFHE работа с шифротекстами чисел с плавающей запятой не увеличивает дополнительную потерю точности. Это означает, что сложение не увеличивает верхнюю границу относительной ошибки, в то время как умножение повышает верхнюю границу относительной ошибки до, как и операция с открытым текстом числа с плавающей запятой.

Доступность данных

Данные, использованные для подтверждения выводов этого исследования, можно получить у соответствующего автора по запросу.

Конфликт интересов

Авторы заявляют об отсутствии конфликта интересов в отношении публикации этой статьи.

Благодарности

Эта работа была поддержана Национальным фондом естественных наук Китая (61572263, 61502251 и 61502243), Исследовательским проектом естественных наук Университета провинции Цзянсу (14KJB520031) и Проектом Фонда постдокторской науки Китая (2016M601859).

Шифрование, криптография и теория чисел — данные, математика, информация и алгоритмы

Криптография — это подраздел прикладной математики , занимающийся разработкой схем и формул для повышения конфиденциальности сообщений за счет использования кодов. Криптография позволяет своим пользователям, будь то правительства, военные, предприятия или частные лица, сохранять конфиденциальность и конфиденциальность при общении. Шифрование — это любая форма кодирования, шифрования или секретной записи.Следовательно, шифрование данных включает в себя любые попытки скрыть, зашифровать, закодировать или зашифровать любую информацию. Однако в современном мире термин «данные» обычно подразумевает цифровые данные, то есть информацию в форме двоичных цифр («биты», чаще всего обозначаемые как единицы и нули).

Целью шифрования является «защита от взлома» (т.е. возможность декодирования и понимания только авторизованными получателями). Криптография также является средством обеспечения целостности и сохранности данных от несанкционированного доступа.Современные криптографические системы полагаются на функции, связанные с продвинутой математикой, включая специализированный раздел математики, называемый теорией чисел , который исследует свойства чисел и отношения между числами.

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

В дополнение к улучшениям, внесенным в криптологические системы на основе информации, опубликованной в рамках секретных государственных исследовательских программ, международные научно-исследовательские организации, занимающиеся исключительно развитием криптографии (например, Международная ассоциация криптологических исследований (IACR)), начали применять приложения математическая теория чисел для повышения конфиденциальности, конфиденциальности и безопасности данных.Приложения теории чисел использовались для разработки все более сложных алгоритмов (то есть пошаговых процедур для решения математических задач). Кроме того, по мере роста коммерческого и личного использования Интернета становилось все более важным не только хранить информацию в секрете, но и иметь возможность проверять личность отправителя сообщения. Криптографическое использование определенных типов алгоритмов, называемых «ключами», позволяет ограничить информацию определенной и ограниченной аудиторией, чьи личности могут быть аутентифицированы.

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

Хотя часто спорили о том, был ли алгоритм , который впоследствии стал известен как RSA , был, по крайней мере, его частью, разработанным ранее правительственными спецслужбами, в августе 1977 года Рональд Ривест, Ади Шамир и Леонард Адлеман опубликовали алгоритм, предназначенный для стать крупным достижением в криптологии. Алгоритм RSA, лежащий в основе системы, основан на сложности факторизации очень больших составных чисел.С 2003 года алгоритм RSA стал наиболее часто используемым алгоритмом шифрования и аутентификации в мире. Алгоритм RSA использовался при разработке интернет-браузеров, электронных таблиц, анализа данных, электронной почты и программ обработки текстов.

Поскольку цифровые данные являются числовыми, их эффективное шифрование требует использования шифрования, а не кодирования. Шифр — это система правил для преобразования любого текста сообщения (открытого текста) в явно случайный текст (зашифрованный текст) и обратно.Цифровые компьютеры идеальны для реализации шифров; практически все шифрование сегодня выполняется на цифровых данных с помощью цифровых компьютеров.

Как простые числа используются в криптографии? »Science ABC

Хакеру или вору, пытающемуся взломать 400-значный код шифрования, скрывающий данные вашей кредитной карты, с помощью компьютера, который проверяет 1 миллион комбинаций в секунду, потребуется около 10 в 194 секундах, чтобы совершить подвиг. . Вселенной 10 возведено в степень 18 секунд.Насколько мне известно, взлом такого кода кажется довольно утомительной задачей.

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

На самом деле открытия, касающиеся простых чисел, почитались просто за сущность открытия — за раскрытие и осмысление скрытых сложностей математики. (Фото: Wallpoper / Wikimedia Commons)

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

Trapdoor

Простые числа обычно называют «атомами» числовой области, поскольку они являются фундаментальными неделимыми единицами, составляющими каждое число.Например, 10 можно записать как произведение 2 и 5, двух простых чисел. Или 150 как произведение 15 и 10, которое можно далее разбить и записать как произведение 3, 5, 2 и 5 — всех простых чисел. Или большее число, такое как 126, 356, которое составлено из больших простых чисел 2,2,31 и 1019.

Этот процесс уменьшения составного числа до произведения простых чисел известен как разложение на простые множители. Для компьютера умножение двух простых чисел, каждое из которых состоит даже из 100 цифр, не составляет или , однако разложение продукта обратно на его компоненты, как известно, сложно даже для суперкомпьютеров.Именно этот недостаток использовали Ривест, Шамир и Адлеман для создания шифрования RSA в 1977 году. На жаргоне криптографии эта однонаправленность известна как «лазейка».

Для компьютера перемножить два простых числа, каждое из которых состоит даже из 100 цифр, не так уж и сложно, однако разложить продукт обратно на его компоненты, как известно, сложно даже для суперкомпьютеров. (Фото: Pixabay)

Ключи

Допустим, C является произведением двух простых чисел P и Q.Например, при шифровании данных вашей кредитной карты число C используется для генерации «открытого» ключа. Этот ключ, как следует из названия, является общедоступным, что означает, что он может быть перехвачен и прочитан кем угодно в сети. Известно, что банки используют открытые ключи длиной 617 цифр для защиты ваших частных транзакций.

Открытый ключ защищает личную информацию, запирая ее в ящике, ручки которого плотно закрыты кодовым замком, состоящим из нескольких сотен цифр. К самому ящику может получить доступ кто угодно, но к содержимому внутри него — нет.Хотя вор может украдкой украсть коробку, он не может открыть ее, не зная комбинации, не обладая «личным» ключом. Этот закрытый ключ принадлежит только отправителю и получателю контента — банку и вам, владельцу кредитной карты.

Закрытый ключ состоит из двух простых чисел P и Q, которые были перемножены для получения открытого ключа C. Без их ведома вор, чтобы заглянуть внутрь, должен разложить C на множители, что может занять у него тысячи лет, если числа состоят из сотен цифр.И поверьте мне, есть лот из огромных простых чисел. Самый большой, который я нашел, это 2 в степени 43 112 609, вычтенной на 1, простота которого была проверена компьютером. Если бы вы написали это число на бумаге формата A4, вам потребовалось бы в общей сложности 4376 листов, да, чрезвычайно толстая стопка из 4,376 листов , чтобы завершить последовательность.

Статьи по теме

Статьи по теме

Наконец, факторизация возможна; это может быть сделано.Просто на это уходит непомерно много времени. По мере развития технологий мы сможем быстрее вычислять цифры. Квантовые компьютеры могут быть очень успешными в достижении этого, но в настоящее время пройдут годы, а возможно, десятилетия, прежде чем они станут полностью функциональными и повсеместными. Наибольшие числа, которые компьютер усердно разложил на простые числа, были: 2 в степени 512 и недавно 2 в степени 768-значного размера.