Въведение

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

Crypto сега е един от многото анонимни технологични герои в нашето ежедневие. Социалните медии, уеб банкирането, военното разузнаване и всяка друга информационна система, която се занимава с чувствителна информация, силно зависи от криптографията. Криптографията ни позволява да имаме поверителност, което някои смятат 12-тото човешко право .

Тази статия ще ви даде въведение в принципите на криптосистемите с публичен ключ и ще ви запознае с тях Сантана Роча-Вили Боас (SRVB) , криптосистема, разработена от автора на статията и проф. Даниел Сантана Роча. По време на писането авторите на алгоритъма подготвят кампания, която включва финансова награда за всеки, който успее да пробие кода. Тъй като статията ще разгледа подробно функционалността на алгоритъма, това е най-доброто място да започнете търсенето си за наградата. Повече информация можете да намерите в Сайт на SRVB .

Какво представлява криптосистемата?

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

Очаква се технологичната надпревара между методите за криптиране и начините за тяхното разбиване никога да няма окончателен победител. Също така, че всяко ново поколение повишава стандартите за информационна сигурност и криптоанализ, което е набор от техники за системно декриптиране / разбиване на криптирани съобщения, т.е. заобикаляне на сигурността или криптирането.

За да могат потребителите да преценят, че криптосистемата (предвид криптографската техника) е сигурна, тя трябва да има одобрението на международната общност от експерти и следователно да бъде публично известна, което е известно като Принцип на Керкхофс . Това условие обаче излага системата на контрол от глобалната криптоаналитична общност, която ще се опита да измисли начини за системно разбиване на криптирането.

Как можете да направите определен процес на криптиране достатъчно таен, за да могат само опитваните агенти да го пробият, като същевременно са достатъчно публични, за да може глобалната криптоаналитична общност да потвърди своята стабилност? Отговорът е компонент, който е ключов елемент на криптологията: ключът. Ключът на криптосистемата е параметър за алгоритмите за криптиране или декриптиране или и за двата. Чрез запазване на параметрите в тайна, а не на семейството алгоритми, могат да бъдат постигнати и двете противоречиви изисквания. Докато семейството от параметри е достатъчно голямо (евентуално безкрайно) и всеки от неговите компоненти може да се докаже, че притежава адекватни свойства, за атакуващите няма да е възможно да определят параметрите само чрез проверка.

И накрая, за да работи ключът ефективно, той трябва да бъде създаден лесно, но почти невъзможно да се отгатне. С изчислителната мощ на съвременните компютри, компютърът ще отнеме по-малко време, за да пробие генериран от човека ключ, отколкото всеки човек някога би трябвало да си представи, плюс не е изгодно да генерира ключове по този начин така или иначе. Поради това ключовете са склонни да се генерират от алгоритъм.

Алгоритъмът за генериране на ключове не трябва да създава предвидими / възпроизводими изходи в резултат на типично използване. Тъй като алгоритмите изпълняват процедури без никакви интелигентни процеси, въпросът е как това може да се направи. Отговорът е да конвертирате алгоритмите за генериране на ключове в карти, които трансформират голям брой наистина произволни битове в ключове. Наистина случайни битове могат да бъдат получени от операционната система, което ги генерира от несигурност във Вселената. Някои източници биха били движение на мишката, забавяне на мрежовия пакет или дори специален хардуер, в зависимост от приложението.

---

Криптосистеми с публичен ключ

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

Досега сме виждали създаването на сигурна комуникация, след като секретните параметри (ключове) са били сигурно обменени, но проблемът с обмена на параметрите чрез публичен канал остава. На този етап ще представим концепция, която решава малко по-осезаем проблем: създаване на сигурен канал.

Да предположим, че Алис работи с Боб и те искат да запазят своите работни взаимодействия защитени чрез криптиране. Те могат да намерят и обменят ключовете си за шифроване, като предадат USB флаш устройство с ключовете си. Но какво, ако Алис и Боб са разположени на различни континенти? Как да установя сигурен канал там, където го няма?

Изпращането на ключове по имейл не би било опция, тъй като неговата конкурентка Ева може да прихване обмена и да използва ключовете си, за да прочете всички криптирани данни по-късно. Ако имаха друг цифров канал, чрез който да могат да предават тази чувствителна информация, тогава нямаше да се нуждаят от криптиране и следователно ключове на първо място. Изпращането на ключа чрез физическа поща също може да бъде прихванато, тъй като за начало е необходимо да се обменя поверителна информация. Изпратете един stegangraphed ключ, скриващ се в други данни би било умно, но безполезно, освен ако подателят не е сигурен, че получателят и само получателят е наясно със съществуването на такова съобщение и знае как да го извлече. Случва се така, че осъзнаването на съществуването на съобщение заедно с описанието на това как да се извлече ключът от данните е един вид ключ, който ни води до началната точка.

Решението е проектирането на криптосистема, за която параметърът за шифроване не е достатъчен, за да изпълни разумно оригиналното съобщение. ^[един] , и запазване за вас параметъра, който ще ви позволи да интерпретирате съобщението. Ние наричаме този параметър частен ключ. Въз основа на частния ключ, може осъществимо да се генерира набор от параметри за инструмент за криптиране, без тези нови параметри да разкриват какво представлява частният ключ. Този набор от параметри може да се споделя публично, тъй като не е толкова важно кой може да шифрова нещо, стига само един човек да може да го дешифрира. Тъй като този набор от параметри за инструмента за криптиране може да бъде направен публичен, той се нарича публичен ключ.

Криптографията, при която ключовете за криптиране и дешифриране се различават и първите не могат да бъдат използвани за извеждане на втората, се нарича асиметрична криптография, докато симетричната криптография е това, което имаме, когато тези ключове са еднакви или лесно могат да бъдат направени един от друг. Алис изпраща на Боб своя публичен ключ, който може да се използва само за шифроване на неща, които само тя може да дешифрира (със своя частен ключ, който тя запазва в поверителност) и, обратно, Боб изпраща Алис нейния публичен ключ, който може да се използва само за криптиране на неща че само той може да дешифрира (използвайки неговия частен ключ, който той също държи частен). Но как можете да публикувате параметър за алгоритъм за криптиране, от който не може да се изведе точният обратен алгоритъм?

Отговорът се крие в областта на математиката, по-свързана с програмирането, теория на изчислителната сложност . Всеки, който се е задълбочил достатъчно в математическите задачи, е чувал за трансформации, които е лесно да се направи по един начин, но е трудно да се направи обратното. Например в смятането, намирането на производно на учебник обикновено е просто упражнение, докато се прави обратното (като решаване на която и да е физическа част или леко нетривиален физически учебник ODE или PDE например) изисква по-разследващ процес на първата хипотеза за семейства от функции, които са гарантирани (или поне правдоподобни), за да съдържат решенията (ите) и да решават обратни проблеми, за да се намерят решения на тези семейства.

Пример, който всъщност се използва в RSA криптосистема умножава страхотни прости числа, вместо да разчита на резултата продукта, без да знае факторите. Умножението е тривиално, но факторингът изисква да сте на случаен принцип ^[2] познайте основните фактори, които имат стотици цифри. Важно свойство на операцията е необходимостта от добро мащабиране. Добавянето на няколко цифри над размера на простите числа в RSA ще доведе до ключ, който изисква хиляди повече операции за дешифриране и ще добави малко увеличение на сложността на процеса на криптиране. Най-общо казано, произведението на прости числа се използва за криптиране, докато двойката прости числа се използва за дешифриране.

Имайки предвид всичко това, нека да разгледаме как работи криптографската система SRVB.

Основният алгоритъм: изследвайте SRVB

Проблемът за сумата на подмножеството

Както всяка друга криптосистема с публичен ключ, SRVB разчита на трудността при решаването на определен проблем, който е лесен за производство. В случая на SRVB това е Проблем със сумата на подмножеството , което може да бъде описано по следния начин:

Dado el entero $ w $ и $ v_1, cdot cdot cdot, v_N in Z $ encuentra la secuencia $ b_1, cdot cdot cdot, b_N in {0,1} $, като $ sum_ {i = 1} ^ {N} v_i b_i = w $.

Ясно е, че този проблем може да възникне чрез произволен избор на N цели числа, произволен избор на подмножество от тях и обобщаване на това подмножество, което е тривиално.

Търсене на груба сила би имало сложност от $ O (N * 2 ^ N) $, изчислявайки за всяка комбинация от стойности от $ b $ s. По-ефективен подход беше даден от Хоровиц и Сахни през 1972г , със сложност от $ O (N * 2N / 2). Проблемът е поне толкова труден, ако заменим $ b $ s и $ w $ с $ k $ - размерни вектори на цели числа. Въпреки това, обхватът, в който трябва да се извърши този по-труден проблем, също трябва да има a изоморфизъм с [пръстен] (https://en.wikipedia.org / wiki / Ring_ (math)), където се извършва по-лесна версия на същия проблем, както ще видим по-нататък. Поради тази причина SRVB експлоатира проблема за сумата на подмножеството в Гаусови цели числа , където $ k = 2 $ ..

Има специален случай, когато този проблем е лесен за изчисляване чрез алчен алгоритъм. Ако поръчаме последователност от мащабни фактори $ v_1, cdot cdot cdot, v_N $, при които всяко цяло число в последователността е по-голямо от сумата на всички цели числа, които са го предшествали ($ forall i, sum_ {j = 1} прекомерна последователност на увеличение .

Ето просто описание на алчното решение за този случай:

1. Започва с $ i = N $, наблюдаваният в момента фактор, и $ w ’= w $, остатъкът от $ w $

2. Ако текущият мащабен фактор е твърде голям, за да побере остатъка от $ w $, това означава, че $ v_i> w '$, задайте $ b_i = 0 $ и продължете към следващата стъпка. В противен случай знаем, че коефициентът на мащаба трябва да е в последователността (тъй като останалите фактори са по-малко от $ v_i $) и затова поставяме $ b_i = 1 $.

   как да напиша спецификация за дизайн

3. $ w ’ Leftarrow w’ - v_i * b_i $, $ i Leftarrow i - 1 $. Si $ i> 0 $, vuelve al paso 2.

4. Уверете се, че сега $ w '== 0 $, в противен случай проблемът е повреден.

Това работи, тъй като знаем, че всички множители, по-малки от наблюдавания в момента, не могат да покрият колективно толкова от (под) сумата $ w '$, колкото текущия множител. Така че, ако оставащата сума е по-голяма от текущия фактор, знаем със сигурност, че всички следващи фактори заедно няма да могат да бъдат обобщени без помощта на текущия фактор. От друга страна, тъй като всички мултипликатори са положителни, ако текущият фактор $ v_i $ е по-голям от останалата сума $ w '$, добавянето на който и да е друг фактор би довело до резултат, надвишаващ $ w' $ още повече.

Ще създадем анотация за останалата част от статията. Избираме $ v_1, cdot cdot cdot, v_n $ и $ w $ да бъдат факторите и сумата на последователността на суперинкремента, докато $ u_1, cdot cdot cdot, u_n $ и $ y $ ще бъдат публично достъпни параметри, които се предоставят за извличане на $ b_1, cdot cdot cdot, b_n $.

С последователност $ u_1, cdot cdot cdot, u_n $, избрана да не е супер страхотна, и числото $ y $ е публично достъпно, не се предоставя достатъчно информация за извличане на последователността $ b_1, cdot cdot cdot, b_n $. Ако обаче има супер страхотна последователност $ v_1, cdot cdot cdot, v_n $, която може да заеме мястото на последователността $ u_1, cdot cdot cdot, u_n $, тази последователност може да се използва за решаване на проблем с алчен подход.

Ще покажем как работи това по-долу.

Използване на суми от подмножества в по-стара криптосистема

В 1978, Ралф Меркъл и Мартин Хелман , те измислиха начин да използват тези две парадигми на раницата и линейност на модулната операция за изграждане на връзката между двете последователности, описани в предишния раздел, като по този начин се създава криптосистема с публичен ключ. Идеята беше да се трансформира лесна раница (този, който се състои от супер нарастващия вектор на целите числа) в твърдия (този, който няма това свойство) посредством линейна операция (модула) с тайни операнди. Трансформацията се състои в умножаване на всеки $ v_i $ по $ theta $ и вземане на остатъка от този продукт по $ alpha $, където $ alpha gt sum_ {i = 1} ^ N v_i $ и $ gcd ( alpha, theta) = 1 $ (две ограничения, които скоро ще бъдат оправдани). Резултатът, последователността $ u_1, ldots, u_N $, вече не се увеличава и може да се счита за a трудна раница .

Случайна пермутация на последователността $ u_1, ldots, u_N $ ще бъде дадена на страната, която иска да шифрова и ни изпрати съобщение. Пермутацията се прави така, че трета страна трудно отгатва каква е оригиналната последователност на суперувеличаване. Битовите блокове на съобщението се използват като коефициенти $ b_1, ldots, b_N $. Криптирането се извършва чрез умножаване на последователността на ключовете с тази последователност от коефициенти и добавяне на умноженията в резултат, който трябва да обозначим с $ и $. Само собственикът на частния ключ може да трансформира $ y $ в съответния $ w $, който би бил получен, ако същите $ b_1, ldots, b_N $ блокове бяха умножени с лесни цели числа (последователността $ v_1, ldots, v_N $). Това се прави чрез умножаване на $ y $ по $ theta ^ {- 1} $, обратна мултипликативна на $ theta $ модул $ alpha $ (чието съществуване зависи от това условие на $ gcd ( alpha, theta) = 1 $). С други думи, $ ( theta * theta ^ {- 1}) bmod alpha = 1 $. След това изчисляваме $ w = (y * theta ^ {- 1}) bmod a $. Причината, поради която това е гарантирано да работи, е линейност на модула , тоест линейната комбинация от остатъците е равна на останалата част от линейната комбинация.

Ако последователно прилагаме дефиницията на $ u $, факторния пръстен и линейността на оператора на модула, ще видим съответствието:

$ begin {align} y & = sum_ {i = 1} ^ N b_iu_i newline & = sum_ {i = 1} ^ N b_i (v_i * theta bmod alpha) newline & = sum_ { i = 1} ^ N b_i * v_i * theta bmod alpha newline & = left [ sum_ {i = 1} ^ N b_i * v_i * theta right] bmod alpha newline & = ляво [ sum_ {i = 1} ^ N b_i * v_i дясно] * theta bmod alpha newline & = w * theta bmod alpha end {align} $

И така лесната сума $ w $ може да бъде извлечено чрез умножаване на двете страни с $ theta ^ {- 1} $ и вземане на модула с $ alpha $. За да направите това, човек трябва да знае както $ alpha $, така и $ theta $ (които позволяват лесно да се изчисли $ theta ^ {- 1} $), които трябва да бъдат частни като част от частния ключ.

Единично ограничение, $ alpha gt sum_ {i = 1} ^ N v_i $, не беше оправдано и ето обяснението: равенството между втория и третия ред се състои от равенство между видове отпадъци от частен пръстен на целите числа по модул $ alpha $. С други думи, той задава равенството само на останалите членове, когато се дели на $ alpha $, което не е достатъчно условие за равенството на членовете . В резултат на това повече от един вектор от $ b $ стойности могат да бъдат картографирани в един $ y $, което се избягва чрез ограничаване на $ w $ да бъде по-малко от $ alpha $ за всяка комбинация от $ b $ стойности.

Както всеки друг случай от ежедневието, пълното познаване на всички хипотези често е невъзможно и никога лесно. В резултат на това трябва да разчитаме на математическа интуиция, когато преценяваме дали криптографската система е безопасна за използване, което не ни предоставя реални гаранции. Шест години след създаването си, MH криптосистемата скъса с a атака от А. Шамир . Имаше още няколко опита за съживяване на МЗ, много от които също се провалиха.

---

Криптосистемата Santana Rocha - Villas Boas (SRVB)

През 2016 г., след малко мозъчна атака с автора на тази статия за ^[3] Вдъхновен от възможностите на криптосистема, Даниел Сантана Роча имаше идеята да замести $ theta $ и $ alpha $ с Гаусови цели числа. По по-технически причини този подход води до съпротива срещу гореспоменатата атака на Шамир.

Той също така е замислил блок от битове, състоящ се от много стъпки от описаната по-рано линейна комбинация от a напа дура . Във всеки от тях в края на последователността ще бъде добавено ново цяло число (Gaussian), еквивалентно на едно, по-високо от сумата на всички предишни, докато най-малкото число ще бъде премахнато.

Различно, но елегантно аналогично ограничение се прилага за $ alpha $, което сега е цяло число на Гаус. Изискваме за $ w leq vert alpha vert ^ 2 $, където $ w $ е, отново, най-високата линейна комбинация от естествените цели числа в лесната раница. Причината е много трудна за формализиране, но за щастие може лесно да се познае от елегантно описание:

Представете си квадратна решетка в комплексната числова равнина, чиято страна е хипотенуза на правоъгълен триъгълник на крака a и b, успоредни на реалната и въображаемата ос. Пример за такава решетка е даден по-долу. Целите числа на Guassian по модул $ alpha = a + bi $ могат да бъдат представени от точки, разположени в рамките на решетката. В рамките на тази мрежа има $ vert alpha vert ^ 2 $ различни точки. Ако изберем достатъчно голям $ alpha $, можем да поберем всички линейни комбинации от лесната раница. Така че ние поставяме изискване за $ w leftarrow vert alpha vert ^ 2 $, където w е [както е описано].

Това е графичното представяне на изоморфизма $ f: Z / n rightarrow Z [i] / ( alpha) $, където $ n = 13 $ и $ alpha = a + bi = 3 + 2i $ (имайте предвид, че $ n $ и $ alpha $ всъщност удовлетворяват $ n = vert alpha vert ^ 2 = a ^ 2 + b ^ 2 $ според изискванията). Точките представляват целите числа на Гаус, тоест комплексните числа $ a + bi $, където $ a $ и $ b $ са цели числа. Както обикновено, хоризонталната ос представлява реалната част, докато вертикалната представлява въображаемата част. Следователно преместването на точка надясно или наляво е еквивалентно на добавяне съответно на +1 или -1 към текущата й стойност. По същия начин преместването на точка нагоре или надолу е еквивалентно на добавяне съответно на + i или -i.

Червените точки са еквивалентни на $ 0 bmod ( alpha) $. Освен тях оцветяваме още 4 двойки точки.

Цвят	Еквивалентно на ... mod α
Оранжево	$ 1 $
Зелено	$ i $
Син	$ -1-i $
Виолетово	$ 1-i $

Изоморфизмът $ f $ се дефинира чрез преобразуването на $ i $ -тия елемент на цикличната последователност $ (0,1,2, cdot cdot cdot, 10,11,12,0,1,2, cdot cdot cdot) $ в $ i $ -тия елемент на също цикличната последователност от точки на фигурата, който се придържа към следните правила:

1. Започнете от червената точка на първия ред;
2. Следвайте десните хоризонтални стрелки; освен това
3. Когато следвате стрелките, изваждате последователността от решетката, тя ще достигне една от не-черните точки. Вместо да отиде до тази точка, той скача към една и съща цветна точка (т.е. еквивалентният точков модул $ alpha $) в рамките на същия квадрат; и накрая
4. Когато тази нечерна точка стане червена (което се случва, след като всички останали цветове са преминали), последователността скача до горната червена точка, като по този начин рестартира цикъла;

За да картографирате поне $ Y $ естествени цели числа, вземете квадрат с площ $ vert alpha vert ^ 2 $ (където $ vert alpha vert = sqrt {a ^ 2 + b ^ 2} $ е от Теорема на Питагор , измерването от ваша страна) поне толкова високо.

Забележете, че всеки 'скок' променя номера на реда $ r $ на $ r leftarrow (r + b) (mod a + b) $, ако броите редовете отгоре надолу и, еквивалентно, на $ r leftarrow ( r + a) (mod a + b) $, ако се брои отдолу нагоре. Следователно, необходимото и достатъчно условие за всеки ред (и точка) да бъде преминат точно веднъж във всеки цикъл е размерът на скоковете да е съпоставен с броя на редовете или, с други думи, $ gcd (a, a + b) = gcd (b, a + b) = 1 $. Поради свойствата на най-големия оператор на общ делител, и двата са еквивалентни на $ gcd (a, b) = 1 $.

Y. S. Villas Boas отбеляза необходимостта от съкровище от $ a $ и $ b $. За да се запази суперинкремент, всяко ново цяло число $ w $, добавено в края на последователността, трябва да надвишава сумата на всички текущи ($ w> sum_ {i = 1} ^ k v_i $). Забелязахте, че за да постигнете това, вашите коефициенти на умножение $ b_i $ ще трябва да бъдат поне 1 и следователно всеки бит не може да бъде преобразуван в коефициенти 0 и 1. Ако коефициентите са 0 и 1, само съставният блок само за един би задоволил суперувеличаването. Поради тази причина битовете 0 и 1 бяха съответно преобразувани в коефициенти на умножение 1 и 2.

И накрая, и по по-малко тривиален начин: по време на всяка стъпка на декодиране се намира ново цяло число $ v_1 $ като решение на уравнението $ b_1 v_1 = v_ {n + 1} - sum_ {i = 2} ^ {n} b_i v_i $, където всички $ v_i $ и $ b_i $ са известни с $ 1

Окончателна техническа характеристика за разрешаване е случаят, когато размерът на съобщението в байтове не е кратно на размера на блока. С други думи, какво да направя с възможните останали байтове на последния блок данни, така че след извличането на блоковете с данни да се запазят всички байтове на оригиналното съдържание, но не повече от тях? Решихме го, като повторихме последния байт на съобщението веднъж. След това това копие е последвано от произволна последователност, в която всеки компонент се изисква само да се различава от предишния. Следователно, когато блоковете с данни се извличат, последният от тях или, в най-лошия случай, този преди последния той е съкратен при последното повторение на байта. ^[4]

Сега ще покажем пример за криптографската система SRVB.

Започваме с параметрите:

как да създадете консултативен съвет

$ k = $ 4;

$ m = 4 $;

което създава дължина на блок от $ l = 4 * 4 = 16 $ и супер невероятна последователност от $ k + 1 = 5 $ естествени цели числа, която се управлява —_, т.е. линейно се комбинира, заедно с резултата от тази линейна комбинация , и намален до последните си k + 1 елемента _— m = 4 пъти;

За по-голяма простота, нека следното да бъде (супер невероятен) вектор на $ v_i $:

$ (1,2,4,8,16) $

Всъщност последователността на първите пет степени на 2, просто защото това е супер страхотната последователност с пет елемента и строго най-малките възможни стойности (като по този начин се избягва 0 в публичния ключ, което тривиално ще отстъпи на 0 кореспондент)

кое от следните е полезна политика за минимизиране на отпадъците и грешките?

Както казахме по-рано, за $ alpha = a + bi $ целите числа $ a $ и $ b $ трябва да бъдат съвместни и според новото ограничение, споменато, трябва да поискаме $ a ^ 2 + b ^ 2 = vert alpha vert ^ 2 geq W $. Бързото изчисление води до $ W = $ 1,590. Като се има предвид, че $ sqrt {1590} simeq 39.8 $, много удобен $ alpha $ за избор би бил $ alpha = 39 + 40i $, тъй като е достатъчно голям, за да побере изоморфизъм с пръстен от цели числа с поне 1590 компонента, като същевременно задоволява $ gcd (a, b) = 1 $. Също така трябва да изберем $ theta $ така, че $ gcd (a, theta) = 1 $ ^[5] и за предпочитане не твърде ниско, така че $ (a_1 * theta) \% alpha neq v_1 * theta $, (също за да се избегне даването на информация). $ theta = 60 $ върши работата, като произвежда:

$ -19-1i, 1 + 38i, 3-3i, 6-6i, $ 12-12i ^[6]

Тогава нека си изцапаме ръцете. Вземете съобщението b. Първо го картографираме към байтов масив съгласно [ASCII] (https://en.wikipedia.org/wiki/ASCII#8-bit_codes) и нашата конвенция за отрязване на блокове данни:

Hola ApeeScape!

Тъй като нашият блок с данни е с дължина 16 бита = 2 байта, а нашето съобщение е с дължина 13 знака, в крайна сметка получаваме 7 блока данни с по 2 байта, където последният съдържа двукратно битово представяне на символа „!“. Ще кодираме първия блок стъпка по стъпка. Обърнете голямо внимание, защото битовете на всеки байт са взети по реда на тяхното значение.

$ m = 01001000 01100101 $

• Първа хапка от първи байт: $ (0,0,0,1) rightarrow (1,1,1,1,2) cdot (-19-1i, 1 + 38i, 3-3i, 6-6i, 12 -12i) = 15 + 4i $
• Второ хапване на първия байт: $ (0,0,1,0) rightarrow (1,1,1,2,1) cdot (1 + 38i, 3-3i, 6-6i, 12-12i, 15 + 4) = 49 + 9i $
• Първа хапка от първи байт: $ (0,1,0,0) rightarrow (1,1,2,1,2) cdot (3-3i, 6-6i, 12-12i, 15 + 4i, 49 + 9i) = 106-10i $
• Segundo хапване на грунд байт: $ (0,1,1,0) rightarrow (1,1,2,2,1) cdot (6-6i, 12-12i, 15 + 4i, 49 + 9i, 106- 10i) = 252-2i $

И така, ние просто картографирахме

'Той' $ Rightarrow (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) $

Останалата част от шифрованото съобщение е както следва:

“Ll” $ Rightarrow (12-12i, 21-2i, 61-3i, 185-31i, 367-59i) $

„O“ $ Rightarrow (12-12i, 25 + 33i, 65 + 32i, 111 + 44i, 244 + 124i) $

'До' $ Rightarrow (12-12i, 9 + 10i, 46 + 12i, 149 + 5i, 277 + 31i) $

“Pt” $ Rightarrow (12-12i, 3 + 16i, 46 + 12i, 73 + 23i, 201 + 49i) $

“Al” $ Rightarrow (12-12i, 4 + 54i, 44 + 53i, 117 + 193i, 231 + 389i) $

”!!” $ Rightarrow (12-12i, 4 + 54i, 32 + 65i, 63 + 92i, 121 + 247i) $

Сега за дешифрирането имаме $ theta ^ {- 1} = 60 ^ {- 1} = 27 + i $:

$ ($ 'Той' $ Rightarrow) $ $ (12-12i, 15 + 4i, 49 + 9i, 106-10i, 252-2i) * theta ^ {- 1} \% alpha = (16,47 , 93 223 527) $

Сега идва алчният алгоритъм:

Първо, извадихме всеки допринасящ фактор, умножен по един, защото е известно, че те допринесоха поне веднъж за последния, което доведе до:

• Второ хапване на втория байт:

$ T leftarrow (527-233-93-47-16) = 148 $

$ (T geq 223) = (148 geq 223) = невярно Rightarrow b_1 = 0; T лява стрелка (T - 0 * 223) = 148 $

$ (T geq 93) = (148 geq 93) = вярно Rightarrow b_2 = 1; T лява стрелка (T - 1 * 93) = 55 $

$ (T geq 47) = 55 geq 47) = вярно Rightarrow b_3 = 1; T лява стрелка (T - 1 * 47) = 8 $

$ (T geq 16) = 8 geq 16) = false Rightarrow b_4 = 0; T лява стрелка (T - 0 * 16) = 8 $

Резултат: 0110;

Остатък: 8 (добавен в началото на последователността като нов най-нисък елемент);

Премахнете 527 от края на текущата последователност;

• Първа хапка от втория байт:

$ T ляво (233-93-47-16-8) = 59 $

как да създавате шрифтове във photoshop

$ (T geq 93) = (59 geq 93) = false Rightarrow b_1 = 0; T лява стрелка (T - 0 * 93) = 59 $

$ (T geq 47) = (59 geq 47) = вярно Rightarrow b_2 = 1; T лява стрелка (T - 1 * 47) = 12 $

$ (T geq 16) = (12 geq 16) = false Rightarrow b_3 = 0; T лява стрелка (T - 0 8 16) = 12 $

$ (T geq 8) = (12 geq 8) = вярно Rightarrow b_4 = 1; T лява стрелка (T - 0 * 12) = 4 $

Резултат: 0101;

Оставащи: 4 (добавен в началото на последователността като нов най-нисък елемент);

Оставете 233 от края на текущата последователност;

• Второ хапване на първия байт:

$ T leftarrow (93 - 47 - 16 - 8 - 4) = 18 $

$ (T geq 47) = (18 geq 47) = false Rightarrow b_1 = 0; T лява стрелка (T - 0 * 47) = 18 $

$ (T geq 16) = (18 geq 16) = вярно Rightarrow b_2 = 1; T лява стрелка (T - 1 * 16) = 2 $

$ (T geq 8) = (2 geq 8) = false Rightarrow b_3 = 0; T лява стрелка (T - 0 * 8) = 2 $

$ (T geq 4) = (2 geq 4) = false Rightarrow b_4 = 0; T лява стрелка (T - 0 * 4) = 2 $

Резултат: 0100;

Остатък: 2 (добавен в началото на последователността като нов най-нисък елемент);

Изпуснете 93 от края на текущата последователност;

• Първа хапка от първия байт:

$ T ляво (47-16-8-4-2) = 17 $

$ (T geq 16) = (17 geq 16) = вярно Rightarrow b_1 = 1; T лява стрелка (T - 1 * 16) = 1 $

$ (T geq 8) = (1 geq 8) = false Rightarrow b_2 = 0; T лява стрелка (T - 0 * 8) = 1 $

$ (T geq 4) = (1 geq 4) = false Rightarrow b_3 = 0; T лява стрелка (T - 0 * 4) = 1 $

$ (T geq 2) = (1 geq 4) = false Rightarrow b_4 = 0; T лява стрелка (T - 0 * 2) = 1 $

Резултат: 1000;

Почивка: 1 (добавен в началото на последователността като нов най-нисък елемент);

Изтрийте 47 от края на текущата последователност;

В резултат на това получихме блока с данни: „01001000 01100101“, който съдържа първите два знака „Той“ от нашето съобщение. Не само това, ние също извличаме успешно нашата страхотна последователност от $ (1,2,4,8,16) $ частен ключ.

Другите блокови карти с данни вървят по същия начин.

---

Сравнение с основните криптосистеми с публичен ключ

SRVB е:

1. Напълно безплатно и публично;

2. Значително по-просто и по-лесно за разбиране и изпълнение от И т.н. ^[7] ;

3. Изобилие от ключове и следователно на практика няма разходи, за разлика, например, на RSA , който се основава на прости числа, които са скъпи .

Вече можем да обобщим най-вероятните уязвимости. Тъй като SRVB произлиза от MH, лесно е да се подозира, че би бил уязвим за обобщаване на [атаката на Шамир] (https://en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem#cite_note-2) или някои друго, което го нарушава.авторът имаше основания да вярва, че това няма да е така, тепърва ще бъде потвърдено (което е много типично, когато става въпрос за криптосистеми).

---

Какво следва?

Роча отбеляза някои обобщения за факторните пръстени, които да се използват, което може да доведе до увеличаване на сложността на криптоанализата. Ние също ще проучим тези възможности.

Линейно алгебрично затъмнение

Случва се така, че по време на разработването и документирането на SRVB, Villas Boas излезе с друг подход за подобряване на концепцията за криптосистемата с раници с публичен ключ, който няма да бъде обяснен подробно в този документ, за да не бъде тази статия твърде дълга. и досадно, но ето четка с него. Ако не можете да го разберете, не се притеснявайте, просто следете за следващото ни публикуване на статия, където ще влезем в подробностите по-точно: вижте сумата $ и $ подмножество от, да речем, $ N $ пръстенови елементи на коефициент $ u_i $ (които изоморфно съответстват на положителните числа $ v_i $ на супер нарастващата последователност, както преди) като умножение на вектор на ред от тези $ u_i $ с вектор на колона $ B $ (за двоичен ) на нули и единици ^[8] .

$ y = sum_ {i = 1} ^ n u_i b_i = (u_1, cdot cdot cdot, u_n) ^ T cdot (b_1, cdot cdot cdot, b_n) $ = UB,

където $ b_i в {0,1} $

Сега си представете, че вместо този вектор на $ u_i $, имате вляво матрица V от $ n $ по $ N $ (с $ n [9] n по n матрица R вляво, определяща n по N матрица P:

P = RV

Идеята е, че Боб използва P като своя нов публичен ключ. Поради случайността на R, векторът

$ Y = PB = RV B = RW $

има информацията $ w $, скрита от шум в други редове на V. Боб също изчислява предварително и съхранява вектора на реда S, който удовлетворява:

$ R ^ T S ^ T = e_1 $

Когато Алис изпраща Y на Боб, той намира SY, защото:

$ SY = S (PB) = S ((RV) B) = SRVB = {e_1} ^ T R ^ {- 1} ((RV) B) = $

(засега само определения)

как да създадете бот за телеграма

$ {e_1} ^ T (V B) = {e_1} ^ T W = w $

(Сега, използвайки асоциативност да отмените Rs)

и след това продължете както преди, за да извлечете вектора на $ b_i $ от $ w $ с помощта на алчния алгоритъм.

И така, с една дума, Linear Algebraic Obscuration използва асоциативността на умножението на матрицата (фактът, че бихме могли да разширим термините и след това да оперираме техните компоненти в нов ред, стига да запазим последователността на всички операнди в последователността), за да „линейно“ смесва и след това филтрира (съответно при криптиране и декриптиране) шума към / от $ w $. И в ограничителния случай $ n = 1 $, системата елегантно се връща към оригинала според подхода на Rocha.

Кампанията SRVB: възнаграждаващо предизвикателство

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

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

Благодаря

Тази конкретна статия и целият проект за SRVB Crypto са получили голяма помощ от проф. Чарлз Ф. де Барос , асистент във [Федералния университет на Сао Жоао Дел Рей] (http://www.ufsj.edu.br/). Проф. Барос ни даде технически преглед на самата криптосистема SRVB. Вярвах, че е необходимо да изпратя, преди да се осмеля да публикувам, и че определено ще ми отнеме много повече време да го направя сам.

Освен това бих искал да изразя дълбоката си благодарност на учителя Аднан Адемович за неговата изключително проницателна, внимателна и търпелива работа като редактор на тази публикация. Член.

---

Терминологичен речник

1. Криптология / криптография: Науката / практиката да се направи почти невъзможно да се тълкува съобщение без конкретен набор от инструкции (в този контекст, така нареченият „ключ“), позволявайки на агентите, които споделят тези инструкции, да комуникират сигурно, дори ако бъдат прихванати от трети страни;
2. Стеганография: Науката / практиката за скриване на едно съобщение в друго чрез добавяне на привидно безобидни модификации към последното;
3. Генериране на ключове: картографирането на случайни (очаквани) входове във валидни (произволни) ключове;
4. Шифроване / кодиране: Лесно изчислимото картографиране на едно лесно интерпретируемо съобщение в друго, което е трудно или невъзможно да се интерпретира, като се използва елемент (както е посочено на случаен принцип) този, съответстващ на ключа от (според принципа на Kerckhoffs), познато и публично валидирано) семейство алгоритми;
5. Дешифриране / декодиране: Лесно изчислимото картографиране, състоящо се от обратното на горното, може също да бъде дефинирано от елемент (както е посочен произволно и следователно неизвестен и труден за отгатване от трети страни) _веднъж, този, съответстващ на ключа_ на a (по същия принцип , общоизвестно) семейство алгоритми, което по този начин излъчва оригиналното съобщение, когато е въведено с криптирането;
6. Криптосистема: Триада на семейството алгоритми за кодиране, семейството на съответните алгоритми за дешифриране и алгоритъм за генериране на ключове;
7. Съюзници: Агентите, на които е предназначена комуникацията и от които се очаква да действат в съответствие с правилата на протокола;
8. Врагове / трети страни: Агенти, с които комуникацията не е предназначена, но въпреки това се опитва да шпионира комуникацията и да заобиколи защитата, засилена от криптосистемата;
9. Безопасен канал: Всеки протокол (процедура) за комуникация, който е лесен за използване и в същото време пречи на трети страни да интерпретират по жизнеспособен начин какво означават техните потребители.
10. Несигурен канал: всеки канал (т.е. протокол или процедура), който, както подсказва името му, не е защитен канал;
11. Разбиване на ключ: Процесът на откриване на ключ, използвайки публична информация (като криптирано съобщение или публичен ключ), различен от самия ключ, който трябва да бъде открит и за който не се очакваше да позволи откриването на ключа. Тъй като информацията, получена в резултат на този процес, дава възможност за дешифриране на съобщенията, това е частен случай на ...
12. Разбиване / дешифриране на съобщение: Всеки начин за извеждане на оригиналното съдържание на криптирано съобщение само чрез самото криптирано съобщение и друга информация, която не се очаква да бъде достатъчна за приспадане на оригиналното съдържание;
13. Разбиване на криптосистема: Откриване на систематичен начин за възможно разбиване на всяко съобщение, кодирано от този метод, под какъвто и да е параметър;
14. Принцип / Desideratum / Axiom / Kerckhoffs Закон: Криптологичен принцип, кръстен на холандския криптограф. Огюст Керкхофс , според която, за да може дадена криптосистема да се счита за сигурна, всичко свързано с нея, с изключение на нейните (частни) ключове, трябва да бъде публично известно;
15. Ключ: Тайно параметризиране на криптосистема, което позволява тя да бъде неволно (и вследствие на това прекъсната) от трети страни, като същевременно се потвърждава от криптоаналитичната общност (съгласно принципа на Kerckhoff);
16. Симетрична криптосистема: Всяка криптосистема, в която който и да е параметър за кодиране е достатъчен за лесно извеждане на параметъра за декодиране, и поради тази причина трябва да се запази частна. Човек може да го префразира, като каже, че параметрите за криптиране и декриптиране са еквивалентни на ключа;
17. Симетрия / публичен ключ на криптосистемата: Всяка криптосистема, за която има начин за изразяване на параметрите за кодиране, който не е достатъчен, за да може разумно да се изведе съответният параметър за декодиране, позволявайки да бъде изпратен до съюзници по несигурен канал или дори да бъде публично достъпен и т.н. безопасна среда на канала, където нямаше такава;
18. Публичен ключ: Компонент на асиметрична криптосистема, който е достатъчен, за да параметризира криптирането, но не е достатъчен, за да осъществи приложимо параметъра за декриптиране, т.е.
19. Частен ключ: Компонент на асиметрична криптосистема, който е достатъчен за параметризиране на декриптирането и следователно трябва да се пазят частни и обикновено е достатъчно също така да параметризирате криптирането;

---

^[един] Имайте предвид, че фразите тук дешифриране или дешифриране не се прилагат, защото преди дадена криптосистема (с всички нейни компоненти, включително нейните ключове) е добре дефинирана, не може да се класифицира даден метод за интерпретиране на оригиналното съобщение на криптирането като преднамерена комуникация (дешифриране) или атака (декодиране).

^[2] Въпреки че има техники за подобряване на тази работа по гадаене, все още е много по-трудно да се открият, отколкото да се умножат.

^[3] Първото вдъхновение беше да разгледаме дърво на тау предположения , безкрайно дърво, вкоренено в число 1, чиито други възли се състоят от цели числа, които водят до двоична операция на събиране, изваждане или умножение между предишни възли, вероятно възел, опериран сам. Целта на теорията е свързана с дълбочината в това дърво, в което всяко цяло число се появява за първи път. Очевидно е трудно да се намерят големи числа в долните клонове (дори ако сме отпуснали необходимостта), но е незабавно да се провери дали дадена последователност от операции действително води до даден резултат.

^[4] Това със сигурност не е най-естественият подход, но чрез приемането му се гарантира, че това подпълване на байта (наречено пълнене ) ...

1. Скрива размера на подложката (по различен начин, например от кражба на шифротекст ) и закрива края на съобщението, представяйки избрани атаки с открит текст по-трудно;
2. Подобрете разпределението на битовете възможно най-близо до еднородно;

Ако се знаеше, че последните блокове на всяко съобщение систематично са пристрастни в разпределение, което далеч не е еднакво, нападателят би могъл да се възползва от този факт, за да извърши статистическа криптоанализа, тъй като всяка дадена извадка от съобщения би била статистически по-представителна от обратното. С други думи, последните блокове са статистически по-малко разнообразни, те се превръщат в най-слабите връзки в съобщението.

^[5] Не се заблуждавайте: този най-голям общ делител е Гаусов, докато този по-горе е реален.

^[6] ... Което не е перфектно, защото лесно разкрива факта, че последните три компонента са пропорционални на 1, 2 и 4. Но отново, за по-голяма простота, ще пренебрегнем тази подробност.

^[7] ... което е толкова сложно, че има и такива прословути случаи на неуспех да се прилагат и поддържат протоколи, базирани на него .

^[8] Тук няма да възприемем подхода на Rocha към блок от множество линейни комбинации, което също ни позволява да превключваме на случаен принцип биса, за да ги направим още по-тъмни.

^[9] Макар и не напълно случайно. Транспонирането му трябва да обхваща подпространството, генерирано от вектора $ e_1 = (1,0,…, 0) $.