Пример перевода десятичных чисел в негадесятичную и негавосьмеричную систему счисления

Слегка необычные системы счисления

Система счисления (англ. numeral system или system of numeration) - символический метод записи чисел, представление чисел с помощью письменных знаков.

* * * * *

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

* * * * *

Под позиционной системой счисления обычно понимается p-ичная система счисления, которая определяется целым числом, называемым основанием системы счисления.

Целое число без знака в p-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа p:

x _(p) = a_n a_n-1 ... a₁ a_{0 (p)} = a_np^n-1 + a_n-1p^n-2 + ... + a₁p¹ + a₀p⁰

где a_k это целые числа, называемые цифрами, удовлетворяющие неравенству 0 ≤ a_k < p .

* * * * *

Например, число тысяча триста тринадцать представляется в десятичной системе счисления в виде:

1313₍₁₀₎ = 1*10³ + 3*10² + 1*10 + 3

* * * * *

Помимо стандартных систем счисления по основанию p > 0, существует множество других интересных позиционных систем счисления. Например, можно рассмотреть числа по основанию -10 - "негадесятичную" систему счисления, в которой

...a₄ a₃ a₂ a₁ a_{0 (-10)} =
... a₄*10⁴ + a₃*10³ + a₂*10² + a₁*10¹ + a₀*10⁰ =
... + 10000*a₄ - 1000*a₃ + 100*a₂ - 10*a₁ + *a₀

* * * * *

Например, число тысяча триста тринадцать представляется в "негадесятичной" системе счисления в виде:

1313₍₁₀₎ = 19493_(-10)

19493_(-10) = 1*10⁴ - 9*10³ + 4*10² - 9*10¹ + 3 = 10000 - 9000 + 400 - 90 + 3 = 1313₍₁₀₎

* * * * *

Более того, в "нега-" системах обходятся без отрицательных чисел, так как в них числа с нечетным количеством цифр – положительные, а с четным – отрицательные. Например:

111_(-8) = 1*(-8)² + 1*(-8) + 1 = 64 - 8 + 1 = 57₍₁₀₎

1111_(-8) = 1*(-8)³ + 1*(-8)² + 1*(-8) + 1 = -512 + 64 - 8 + 1 = -455₍₁₀₎

* * * * *

Более подробно о таких системах счисления можно прочитать в великой книге великого Дональда Кнута.

* * * * *

А пока – задание:

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

CEA + DBC + EAD = CDEDA

C A F B 9 9 B F A C H + D G K N N K G D A H = H

1. Кнут, Д.Э. Искусство программирования. Том 2. Получисленные алгоритмы. - Вильямс, 3-е издание. - 2002. Читать ...

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

Неправильный хэш

Слово хеш происходит от английского "hash", одно из значений которого - "путаница" или "мешанина". Это довольно полно описывает реальное значение этого термина. Часто еще используют слово "хеширование" - от английского hashing (рубить, крошить, спутывать и т.п.).

* * * * *

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

* * * * *

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

* * * * *

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

* * * * *

Пример использования хешей в при организации парольного доступа. В системе хранятся не сами пароли, а их хеши

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

* * * * *

А теперь плавно переходим к заданию ...

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

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

* * * * *

К примеру, пароль 65234 будет храниться в виде числа 20. А пароль 12368 – тоже как 20. В теории хэш-функций говорят, что такая пара значений паролей образуют коллизию. Только об этом Василий подумал слишком поздно ...

* * * * *

Ответьте на вопрос: сколько различных паролей из 5 цифр в программе Василия будут "хешированы" числом 33 ?

Ответ введите в виде целого числа. Пробелы - не нужны

1. Криптографические хэш-функции / Сайт cryptowiki.net. Читать ...

Задачи олимпиады Junior.Crypt.2017

Задача 01 от Cicada-Grodno 3301

Цикада 3301 — таинственная организация, публикующая головоломки в Интернете. Первая серия головоломок появилась в Интернете 5 января 2012 года и продлилась около месяца. После было еще несколько серий головоломок. В 2015 и 2017 годах новых головоломок не было.

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

* * * * *

А теперь задача 01.

​Чтобы начать решать наши задачи необходимо знать хотя бы шифр Цезаря.

Зашифрованную строку

учийтеесдзшичёсьтьшйлдзйчы

поможет расшифровать следующая последовательность:

4, 9, 1, 6, 2, 5, 3, 6, 4, 9, 6, 4, 8, 1, 1, 0, ...

* * * * *

Ответ введите строчными (маленькими) буквами. Без пробелов

Задачи олимпиады Junior.Crypt.2017

Задача 02 от Cicada-Grodno 3301

Однажды в сети TOR был обнаружен сайт http://fh63ozjoouyh7iuu.onion/. Как вы видите, сайт расположен в домене .onion, а это значит, что открыть его можно только браузером, настроенным для работы с сетью TOR.

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

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

* * * * *

Тайну эту откроет решение задачи 02.

​ ​Вам дана таблица частот букв алфавита из сообщения

[0.055, 0.008, 0.042, 0.012, 0.025, 0.068, 0.004, 0.012,
0.008, 0.085, 0.017, 0.025, 0.038, 0.025, 0.06, 0.115,
0.047, 0.042, 0.055, 0.094, 0.034, 0.0, 0.012, 0.008,
0.025, 0.012, 0.004, 0.0, 0.012, 0.004, 0.012, 0.004, 0.017]

и зашифрованное сообщение

dgjk ytgh fdjv jxyj bght lgjk j;ty btxn jwbr
flf' njgh jtrn cgtw cke; ,gjg hbdk txty b.rc
jnhe lybx tcnd enfk fynk bdjq vjkj l`;b dgjk
mpe' njqd thcb bujd jhzn vfci nf,s buhs jnvt
nbdi tqcz gjxn byfd ct[r jynb ytyn f[[j nzcl
heuj qcnj hjys yfcn jzob v'yn epbf cnfv gjlc
bkeb ytnf rbti nexr b

Ответьте одним словом на вопрос: "По предположению, чей проект Цикада?"

* * * * *

Ответ введите строчными (маленькими) буквами. Без пробелов

Задачи олимпиады Junior.Crypt.2017

Задача 03 от Cicada-Grodno 3301

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

4 января 2012 года на сайте 4chan был размещен пост: «Привет. Мы ищем лиц с высоким интеллектом. Для этого мы разработали тест. В этом изображении есть скрытое сообщение. Найдите его, и оно покажет вам, как найти нас. С нетерпением ждем тех немногих, кому удастся пройти весь путь. Удачи. 3301».

* * * * *

Что искать - частично откроет решение задачи 03.

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

72 11 42 51 32 63 61 33 23 53 63 61 43 15 53 52 25 45 11 43 52 23 51 11 72 32

* * * * *

Ответ введите одним словом в именительном падеже единственного числа. Строчными (маленькими) буквами. Без пробелов и других разделителей