В данном случае вы описали алгоритм RSA. Это ассимитричное шифрование. Насколько я помню, ассимитричное шифрование достаточно затратное для вычислительных ресурсов действие, по сравнению с симметричным шифрованием (где используется один ключ, как для шифрования, так и для дешифровки) . И именно по этому с помощью ассиметричного шифрования передается не само сообщение , а ключи симметричного шифрования, для последующего обмена закодированной информации. Ну и плюс, нынче RSA уже заменяется всякими эллиптическими кривыми.
В каждом доме 5 квартир. Номер квартиры содержит в себе все ответы: 1 цифра: буква дома 2 цифра: этаж 3-4 цифры: номер квартиры. Нечетный номер - квартира слева, четный - справа. (это определяет в какую сторону выходит квартира на 3 этаже). -Логика нумерации квартир на 1,2 этажах: нумерация ведется от 1 с шагом в 4 (количество квартир на них).
Выглядит: 1-5-11(заменили 9 и 13)-15-19-23-... Причина скачка на 11 - пропуск номера 13, как несчастливого числа. А1 = 1101 - 1102 (1 этаж) , 1201 - 1202 (2 этаж) , 1302 (3 этаж) А2 = 1105 - 1106 (1 этаж) , 1205 - 1206 (2 этаж) , 1304 (3 этаж) (!)А3 = 1111 - 1112 (1 этаж) , 1211 - 1212 (2 этаж) , 1306 (3 этаж) ... -Логика нумерации квартир на 3 этаже: зависит от того в какой стороне расположена. Нечетные слева: 2 * номер дома + 1. Четные справа: 2 * номер дома. Решение: A3, 1 этаж, левый подъезд.
Степени сложности: 0. Узнать про алгоритм шифрования 1. Понять алгоритм шифрования 2. Объяснить алгоритм шифрования 3. Применять алгоритм шифрования 4. Разработать алгоритм шифрования Между 1 2 3 и 4 разница экспоненциальная. Я пока на уровне 0 =(
клёвая тема. тока насколько я знаю, такой несимметричный шифр довольно медленный и поэтому он не используется непосредственно для шифрования. а лишь для передачи реального ключа для более быстрого, симметричного шифрования (т.е. шифрования, в котором шифрование и дешифрование делается одним и тем же ключом). и ещё для цифровых подписей.
Так, в поддержку ролика скорее)) Тема затронута выходящая за рамки "чисто математики" и она может для кого-то стать основой понимания криптографии. Так что стоит упомянуть пару вещей. Это уже не совсем математика, но думаю будет полезно. Всё-таки современное шифрование начиналось с симметричного шифрования и о нём надо что-то знать. Хотя-бы про элементарное исключающее или (XOR): текст XOR пароль = шифр, шифр XOR пароль = текст (вместо букв подставить соответствующие биты). Это самый примитивный алгоритм, хотя при должной подготовке текста и пароля - не такой уж и простой к взлому. Естественно симметричных алгоритмов великое множество. Ну и про открытую шкатулку - не забываем про атаку "men on the middle": отправляешь кому-то открытую шкатулку, ключ от которой есть только у тебя, злоумышленник её прихватывает и отправляет адресату свою шкатулку. Он не зная о подмене кладёт что-то в неё и отправляет назад. Злоумышленник перехватывает, открывает свою шкатулку, достаёт, читает, кладёт в настоящую шкатулку и отправляет тебе. Ты её открываешь своим ключом и думаешь что всё ок... Поэтому в этой теме со шкатулками есть важный компонент: центры сертификации. Которые подтверждают подлинность, а как правило сами выдают эти открытые шкатулки, чтобы не брали где попало что попало.
26! микросекунд - это 4.033 * 10^20 секунд или 1.278 * 10^13 лет или 930 * [возраст вселенной]. Просто для осознания. Даже если перебирать все варианты в таком виде шифрования по одной микросекунде на каждый, нам понадобится столько вот времени (для латинского алфавита).
Борис Викторович, прошу заметить, что формула Ф(q*p)=(q-1)*(p-1) не работает для случая, когда p=q Например: p=q=2. Тогда Ф(p*q)=(p-1)*(q-1)=1*1=1. НО Ф(q*p)=Ф(4)=2 (числа 1 и 3). Следовательно формула Ф(q*p)=(q-1)*(p-1) работает только для p и q таких, что p не равно q. Для p и q таких, что p=q, у меня получилось вывести такую формулу: Ф(p*q)=Ф(p^2)=p*(p-1).
Борис ,здравствуйте ,вы не могли бы рассказать почему в большинстве олимпиадных задач по геометрии дается задание что -либо доказать, почему они сложнее чем найти ,можно увидеть видеоролики по топу самых сложных задач из элементарной геометрии? Как доказывать какие -либо факты,и как понять что вот ,мы доказали. Можно узнать в чем сложность задач по геометрии международного уровня ?Если не трудно будет, расскажите про это :)
Борис Викторович, здравствуйте! Вы сказали в ролике, что число I меньше числа n = pq. Далее, применили Th Эйлера: I^N сравнимо с 1 по модулю n, где N = (p -1)(q - 1) - значение функции Эйлера для числа n. Но, ведь теорема Эйлера доказывается при обязательном условии, что числа I и n взаимно просты, т.е НОД (I, n) = 1. Если тот, кто шифрует информацию берёт I < n, то это не означает, что его I не может оказаться числом кратным р или q (пусть эти кратные меньше, чем n = pq, т.е. требование I < pq - выполнено). Тем более, что p и q это огромные числа и таких кратных (kp < qp и jq < pq), тем больше, чем больше сами числа р и q. Если случайно окажется, что шифровальщик взял, например, I = kp < qр, тогда получаем: НОД(I, n) = р > 1. Но, тогда разве мы можем воспользоваться теоремой Эйлера? Ведь, она верна только для тех чисел I, у которых НОД (I, n) = 1. А, тот кто шифрует информацию (беря I < n) знает n, но не знает p и q. P.S. Правда, я рассмотрел сейчас несколько примеров, - брал маленькие простые: р < q, и затем брал I = ip < qp = n (i - натуральное), ну и, соответственно, брал натуральные числа а и b, такие что аb делится на (р -1)(q - 1) с остатком 1. Затем находил остаток Т от деления (ip)^a на n. Потом, непосредственно (не используя теорему Эйлера), находил остаток от деления Т^b на n и получал, что этот остаток равен I = ip. Нужно попробовать доказать в общем виде, что в том случае, когда, например, I = ip < qp (т.е. НОД(I, n) = р > 1), тем не менее, всё равно Т^b сравнимо с I по модулю n.
@@trushinbv , я заменю, с Вашего позволения, букву Гамма (в левой колонке скриншота) на x (просто Гамма у меня нет на клавиатуре). У меня ещё, тогда, остался вопросик: - почему x^(Nk + 1) = x (mod n). Но, попробую сам разобраться с этим!
@@trushinbv Ну, похоже, разобрался с гаммой (что в левой колонке скриншота) в степени (Nk + 1) Там же фокус в том, что само это число гамма (обозначим его: х) тоже может быть кратным р. У нас: I = хр < qp, т.е. имеем ограничение: х < q < n. Если х взаимно прост с n = pq, то НОД(х, n) = 1. Тогда, применив теорему Эйлера получим: х^(Nk + 1) = x(х^N)^k =х (mod n). Но, ведь (при х < q < n), ничего не мешает числу х быть, как упомянуто выше, кратным р (например, при p^2 < q < n и т.д). Таким образом, пусть х = mр, тогда х^(Nk + 1) = (mp)^(Nk + 1) = m^(Nk + 1)*р^(Nk + 1) = pm^(Nk + 1) по модулю n (доказательство, что р^(Nk + 1) = р (mod p), см скриншот БВ). Ну, ясно, что дальше смотрим на m (оно взаимно просто с n или нет) и, как бы методом спуска, по индукции, идём вниз к некоторому последующему m, взаимно простому с n. Но, можно и по другому. Если I = хр < n (х < q), мы можем разложить I на простые множители и все они будут (лишь, возможно, за исключением некоторой степени числа р) взаимно просты с n. Тогда, обозначим произведение этих простых множителей (взаимно простых с n), как Y (следовательно, Y тоже взаимно просто с n) и число I = хр, запишем, как I = Yр^c (I < n). Тогда: I^(Nk + 1) = (Yр^c)^(Nk + 1) = Y^(Nk + 1)*(p^(Nk + 1))^c = = Y^(Nk + 1)*р^c по модулю р. Но Y и n взаимно просты, тогда применив Теорему Эйлера, получим: Y^(Nk + 1) = Y (mod n). И окончательно: I^(Nk + 1) = Yр^c (mod n), а это, см выше, и есть I = Yр^c.
@@IgorGusev28 Мне казалось, что я ответил, но сейчас обнаружил, что моего ответа нет ( Все проще: - мы поняли, что p^(Nk+1)=p, - аналогично, q^(Nk+1)=q, - если с взаимно просто с n, то с^(Nk+1)=с. А любое число I можно представить как c⋅p^k⋅q^m.
15:18 - нужно разложить фи (n) на множители. не совсем понятно. ведь у числа n всего два множителя-простые p и q? нет? кажется можно создать массив возможных n, и соответствующих ему p и q- и отсюда сразу же найти фи (n)=(p-1)(q-1)? нет?
На самом деле, чтобы расшифровать одноалфавитный шифр замены, достаточно в среднем 5(!) слов. С помощью частотного анализа можно сопоставить символы с самыми частыми буквами типо а,о,с,к и пр. При владении языка, на котором написано сообщение остальные слова уже отгадываются без труда
Я знаю, что применяли такой способ шифрования. Одна буква обозначалась несколькими символами. Символы разные, а буква одна. И ещё, вставлялись ничего не значащие символы. Их надо было просто пропустить. Это применялось не только для букв, но и для знаков препинания, цифр, пробелов между словами. Если одна буква могла обозначается достаточно большим количеством разных символов, и вставлялось достаточно большое количество ничего не значащих символов, правда длина текста увеличивалась раз в пять- шесть, расшифровать текст было практически невозможно.
А3, правый подъезд, первый этаж Решение: 1) От буквы зависит первая цифра номера (в алфавитном порядке) A - 1 B - 2 C - 3 (D - 4) E - 5 2) Вторая цифра номера означает этаж 3) На первом этаже в первом подъезде дома A1 должны быть комнаты 01-02 в одном подъезде и 03-04 в другом. 05-06 это дом A2 и по видео видно что это левый подъезд Тогда 07-08 это дом А2 правый подъезд, далее: 09-10 лп A3 11-12 правый подъезд A3 Значит 1111 это правый подъезд A3 Извиняюсь за немного сумбурное решение, но надеюсь оно понятно.
Имею генератор случайных чисел (ГСЧ). Сначала прокручиваю его, к примеру, на N=1000540001 оборотов (это ключ), потом, получив случ.число, сдвигаю букву шифруемого текста (по какому-то алфавиту) на это число позиций. Посылаю получателю. Дальше всё повторяется для всех букв текста. Получатель имеет такой же ГСЧ. Запускает его и сначала прокручивает его на N оборотов, дальше идёт расшифровка способом движения назад по алфавиту. Просто и почти недоступно взлому и расшифровке. *) Разумеется, имеется в виду генератор псевдослучайных чисел.
Теория чисел конечно применяется в криптографии и не только в ней, но вообще-то её две тысячи лет развивали чисто из интереса. Те кто ей занимались даже гордились, что это чистая математика, которая не имеет практического применения, особенно военного. А в криптографии её начали применять очень недавно, после второй мировой. Одним из первых это предложил Алан Тьюринг, который вместе с группой других британских математиков взломали немецкую шифровальную машину Энигма
A1l = 1301 ? A1r = 1302 (1101-1102, 1201-1202) A2l = 1303 (1103-1104, 1203-1204) A2r = 1304 (1105-1106, 1205-1206) A3l = 1305 (1107-1108, 1207-1208) A3r = 1306 (1109-1110, 1209-1210) A4l = 1307 (1111-1112, 1211-1212) B4l = 2307 (2115-2116, 2215-2216) C6r = 3312 (3123-3124, 3223-3224) E5l = 5309 (5119-5120, 5219-5220) Первая цифра в номере комнаты указывает на порядковый номер литеры домика в алфавите, вторая цифра указывает на этаж. В каждом домике по 10 комнат. В домике А1 левый подъезд скорее всего административный и не участвует в общей нумерации. На это еще указывает смещение нумерации комнат в домиках с литерой А. Ответ: А4, левый подъезд, первый этаж.
с первым и вторым этажами понятно, но третий как-то подозрительно составлен. В доме А2 ожидаешь увидеть на третьем этаже 1303, в доме E5 5310, в доме B4 2308.
Борис Викторович,спасибо вам за видео! Интересует вопрос : планируются ли скидки на курсы в будущем учебном году? Интересует Физика и Математика. Заранее спасибо за ответ.
@@trushinbv прямо алгоритм вижу по расшифровки замененных символов по сочетанию условий : длине слова ++ частота (вероятность) слова + частоте букв n-ой позиции
@@trushinbv да уж, опять темку степеней поднял, весь день маньячил, полтетради исписал, 2 алгоритма разложения на множители довел до ума, ну все равно идеала не получилось, степень раскладывать продолжил, точнее с остатками работал, там уже очевидно, что все упирается в единицу и из пару (двойку). Буду на английский сегодня нажимать, хоть не напрягает. Как ты подчеркнул в одном из видео, что некоторые задачи неделю нужно решать, если бы, некоторые годами(, а некоторые со злостью штурмом решаются
Полно же роликов)) Каждая транзакция записывается в блокчейн. Новая запись это хэш всего, что было до этого (понятно, что считается он сложно). Поэтому задним числом ничего не поменять: придётся пересчитывать весь блокчейн, что нереально. За выполнение записей берут комиссию и получают премию - тот самый майнинг. Копии блокчейна есть у всех желающих. Там написано кто, когда, кому и сколько. Всё. Дальше технические детали. Номера кошельков, правила записи, ЭЦП, правила вычислений, арбитраж и т.д.
А что если закодировать другим способом. Например от 650 до 800 отвечает на букву А. От 801 до 1500 отвечает за пробел. От 1501 до 2000 означает точку. Если мы использовали цифру 650 то мы ее не можем использовать повторно . То есть мы использовали 650 потом на эту же букву используем 651, 652 и тд по очереди. 650 повторно не используем чтобы люди не смогли взломать частотным анализом. После того как мы использовали цифру 800 мы можем использовать цифру 650 и ток по кругу. Цифры не привязаны к языкам. 2001 до 4000 это ловушка. Они нужны чтобы отнять время взломщиков. Эти цифры не несут никакой ценности. Это как сундук с камнями. Камни для веса. И разбойники уходят с пустыми руками ведь сундуки были обманом. Как то так. Благодарю вас
Султан! Я над этим думал лет 45 назад. Но из-за этого шифровка будет длиннее. Буква в компьютере занимает 8 бит, то есть байт. Еще надо иметь несколко бит, которые показывают вариант кодирования этой буквы. Например, буква имеет такой код: 10011100. А после шифрования такой: 11011011 - этот код должен пойти в шифровку. Если добавить к этому коду 4 бита справа, то будеи меть возможность закодировать эту букву 16 вариантами: 000011011011 000111011011 001011011011 ... 111111011011. Но расшифровывать ее будут по байтам, то есть: 00001101 10110001 11011011 00101101 1011... Частотный анализ здесь работать не будет, но информация расширяется в 1,5 раза. Да и не мешало бы продумать в как перемешивать биты.
@@NordKavkaz-i2u почему не будет работать частотный анализ? Хороший криптографический алгоритм открыт для анализа. В данном случае мы будем знать диапазоны. То есть от 801 до 1500 какая то буква. Вот и можем использовать частотный анализ не на числа, а на диапазоны. Если же мы в качестве ключа, будем передавать сами диапазоны. То это ничем не отличается от невзламываемого шифра .
Есть замок ,который гарантирует сложность открывания,есть вор, который знает как вскрыть замок,это обычное соревнование,не связанное с перебором всех комбинаций!!!!Вор легко может сломать механизм и замок,превращает в щеколду,т.е. задача сводится к двоичной задачи,целью математитики является свести задачу к двоичной системе!!!!!!
Ваня Днепров если у вас есть просторе число р (например 3), то для любого целого а (например 6), будет справедливо утверждение: а^(р-1) будет сравнимо с 1 по модулю р (в нашем случае 3). То есть остаток от деления а^(р-1) на р будет равен 1 ( Ето фориулировка в лектора.) Я предлагаю вам проверить будет ли справедливо ето утверждение..
Мне кажется что сейчас уже есть технология разложения числа на простые множители быстро. Это майнинг криптовалюты и сотни ферм для етого. Если я не ошибаюсь, там заложен именно такой механизм. То есть скоро будут известны "все" пари простых чисел. Поправьте если я не прав...
Вам кажется. В майнинге хоть и называется "полезные вычислительные мощности" криптофермы ничего полезного не делают. Там идет простой подбор определнной хешсуммы от последней цепочки блокчейна.
Увы, но малая теорема Ферма не является действенной для проверки простых чисел. Достоверно проверить на простоту числа может только тест Агравала-Каяла-Саксены.
@@trushinbv ну да, просто вы, я заметил, не акцентируете свое внимание на этом. Но, увы, я не математик, а так, просто интересующийся. Благодаря вам много интересного для себя узнал и понял на 4-м десятке лет. Работаю в банковской сфере с достаточно умными и образованными людьми в технической сфере, но есть, на первый взгляд, простые факты, связанные с финансовыми рынками, которые никак пока не поддаются математическим объяснениям.
странно. Для промышленных целей проще обменяться шифроблокнотами (случайными последовательностями символов)и работать как Штирлиц. Просто и убойно. Да, тут нет открытого ключа ну и черт с ним.
1. как обменяться? что бы быть уверенным , шифроблокноты никто не перехватил. 2. Что делать если будет подозрение на компроментацию шифроблокнотов? 3. Что делать при рассинхронизации или провреждении шифроблокнотов? . да это действительно проще и главное более надежнее в случае 2х получателей. Но когда у тебя тыщы микросервисов работающих на сотнях серверов - гоняющие между собой петабайты не всегда полезноой инфы....
@@arxxximed Вот. Как сказал сократ -спрятать камень лучше всего среди похожих камней. Не хрен все шифровать свирепо для тыщ микросервисов-эти сервисы не особо и нужны. 1. Как обменяться? курьером с личным контактом, 2. Условный сигнал на запасной блокнот. 3. Запасной блокнот
@@barackobama2910 погодите. Вы ж сказали в промышленных целях. Это что? два три слова ?)). Ну и какие требования у промышленной передачи данных? 1. Целостность 2. Скорость. Блокноты как раз решают вопрос полного шифрования, исключая скорость и целостность. Нужно срочно передать за 3000 км секретные чертежи, но мы ждем курьера с блокнотом ключей)) А пока курьер приехал, оказалось что флешка курьера "размагнитилась" и пару тыщ цифр в ключах были заменены на случайные или вообще потеряны. Ну и главное , а как спрятать курьера? быть уверенным что его не завербуют по дороге, или еще хуже , он изначально сдает все блокноты?
@@arxxximed Как делал Эрих манштейн. Он слал курьера с секретным приказом а реальный приказ доставлял на словах доверенный унтер на которого никто бы не заподозрил. Так он несколько раз обвел за нос Ватутина. Шифроблокнот присылается в виде порнокартинки на открытом для всех сайте соцсети. Просто получатель знает как найти картинку а шпионы не знают, а картинок в сети миллиарды. Так же и штирлиц давал в газету объявление "бабушка Ильза здорова". Но только получатель знал что это означает. И никто не знает какое объявление и когда кодовое.
сейчас почти все устройства могут производить операции с 600 и больше значным числом. )) смотря какие операции, проблема математической расшифровки всегда в ассиметричности некоторых математических функций. возьмите простое большое число, и возведите в степень этого же числа. Это просто. и компьютер справится с этим очень быстро. А если же попробовать наоборот? Разложить большое число на простые множители? то кроме алгаритма перебора пока ничего не известно..
Не правильная крипто загадка .По количеству и форме иголок вычислить вид сосны , её ареал распространения .И конечно дать правильный ответ - где сейчас аФтар находиться : Крым или "Сочи".?
Есть 2 проблемы:1) кватновые компьютеры на столько кубит узконаправленны и решают другие задачи, 2) многофункциональные квантовые компьютеры почти на 0 уровне развития. Но вообще да, эта технология - конец для нынешней криптографии
Василий Понаморев Нет, не конец. Разработан метод Брассара-Беннета передачи совершенно секретных сообщений по фотонной линии. Там применяются поляризованные фотоны и принцип неопределённости. Короче, это метод одноразовых блокнотов, при этом проблему распределения ключей решают с помощью квантовой физики.
На самом деле даже обидно, что такая мутная для меня область математики настолько применима сегодня. То есть, уже не получится рационализовать своё нежелание ботать тем, что "оно нигде не применяется". Кстати, если хотите изучать теорию чисел - можете пойти на мехмат МГУ. У нас в первом семестре есть предмет Элементы теории чисел, а на факультете существует Кафедра теории чисел, которая принимает студентов.
Какой же всё-таки у вас замечательный контент)
Как же прекрасен Долгопрудный)))
А ха-ха-ха
Это лучшее объяснение алгоритма RSA из всех, что я когда-либо видел!
В данном случае вы описали алгоритм RSA. Это ассимитричное шифрование. Насколько я помню, ассимитричное шифрование достаточно затратное для вычислительных ресурсов действие, по сравнению с симметричным шифрованием (где используется один ключ, как для шифрования, так и для дешифровки) . И именно по этому с помощью ассиметричного шифрования передается не само сообщение , а ключи симметричного шифрования, для последующего обмена закодированной информации. Ну и плюс, нынче RSA уже заменяется всякими эллиптическими кривыми.
В каждом доме 5 квартир.
Номер квартиры содержит в себе все ответы:
1 цифра: буква дома
2 цифра: этаж
3-4 цифры: номер квартиры.
Нечетный номер - квартира слева, четный - справа.
(это определяет в какую сторону выходит квартира на 3 этаже).
-Логика нумерации квартир на 1,2 этажах: нумерация ведется от 1 с шагом в 4 (количество квартир на них).
Выглядит: 1-5-11(заменили 9 и 13)-15-19-23-...
Причина скачка на 11 - пропуск номера 13, как несчастливого числа.
А1 = 1101 - 1102 (1 этаж) , 1201 - 1202 (2 этаж) , 1302 (3 этаж)
А2 = 1105 - 1106 (1 этаж) , 1205 - 1206 (2 этаж) , 1304 (3 этаж)
(!)А3 = 1111 - 1112 (1 этаж) , 1211 - 1212 (2 этаж) , 1306 (3 этаж)
...
-Логика нумерации квартир на 3 этаже: зависит от того в какой стороне расположена.
Нечетные слева: 2 * номер дома + 1.
Четные справа: 2 * номер дома.
Решение: A3, 1 этаж, левый подъезд.
Круто, очень круто!
Не круто только что мне недостаточно интеллекта чтобы понять ваше объяснение, но я думаю что исправлюсь)
Как же этого не хватало в школе... Спасибо большое! :)
Наберите в поисковике: Закон расположения простых чисел найден.
Видео в топы!
Только начал смотреть, уже очень интересно.
и полезно.
Степени сложности:
0. Узнать про алгоритм шифрования
1. Понять алгоритм шифрования
2. Объяснить алгоритм шифрования
3. Применять алгоритм шифрования
4. Разработать алгоритм шифрования
Между 1 2 3 и 4 разница экспоненциальная.
Я пока на уровне 0 =(
Вот что значит на отдыхе! Голос другой!! Реально
клёвая тема. тока насколько я знаю, такой несимметричный шифр довольно медленный и поэтому он не используется непосредственно для шифрования. а лишь для передачи реального ключа для более быстрого, симметричного шифрования (т.е. шифрования, в котором шифрование и дешифрование делается одним и тем же ключом). и ещё для цифровых подписей.
Какой хороший и ПРАВИЛЬНЫЙ пейзаж!
Так, в поддержку ролика скорее))
Тема затронута выходящая за рамки "чисто математики" и она может для кого-то стать основой понимания криптографии. Так что стоит упомянуть пару вещей. Это уже не совсем математика, но думаю будет полезно.
Всё-таки современное шифрование начиналось с симметричного шифрования и о нём надо что-то знать. Хотя-бы про элементарное исключающее или (XOR):
текст XOR пароль = шифр, шифр XOR пароль = текст (вместо букв подставить соответствующие биты). Это самый примитивный алгоритм, хотя при должной подготовке текста и пароля - не такой уж и простой к взлому.
Естественно симметричных алгоритмов великое множество.
Ну и про открытую шкатулку - не забываем про атаку "men on the middle": отправляешь кому-то открытую шкатулку, ключ от которой есть только у тебя, злоумышленник её прихватывает и отправляет адресату свою шкатулку. Он не зная о подмене кладёт что-то в неё и отправляет назад. Злоумышленник перехватывает, открывает свою шкатулку, достаёт, читает, кладёт в настоящую шкатулку и отправляет тебе. Ты её открываешь своим ключом и думаешь что всё ок...
Поэтому в этой теме со шкатулками есть важный компонент: центры сертификации. Которые подтверждают подлинность, а как правило сами выдают эти открытые шкатулки, чтобы не брали где попало что попало.
26! микросекунд - это 4.033 * 10^20 секунд или 1.278 * 10^13 лет или 930 * [возраст вселенной]. Просто для осознания. Даже если перебирать все варианты в таком виде шифрования по одной микросекунде на каждый, нам понадобится столько вот времени (для латинского алфавита).
Борис Викторович, прошу заметить, что формула Ф(q*p)=(q-1)*(p-1) не работает для случая, когда p=q
Например: p=q=2. Тогда Ф(p*q)=(p-1)*(q-1)=1*1=1. НО Ф(q*p)=Ф(4)=2 (числа 1 и 3). Следовательно формула Ф(q*p)=(q-1)*(p-1) работает только для p и q таких, что p не равно q.
Для p и q таких, что p=q, у меня получилось вывести такую формулу: Ф(p*q)=Ф(p^2)=p*(p-1).
1 - не простое, и не составное
Мне кажется, что (p-1)^2 будет вернее, если рассматривать р=q=3
Функция Эйлера мультипликативна в случае взаимопростоты p и q
@@Astromega_p=q=3 тогда n=9, взаимо просты числа это 1,2,4,5,7,8. Тогда N=6. Автор прав p*(p-1)=3*(3-1)=6
@@__misterx__ если рассматривать такой случай, где числа не взаимно просты, то да. А вот в случае, когда ~(p:q), получается ф(pq)=ф(р)*ф(q)
Спасибо большое
Сразу вспомнился фильм Игры разума)
Очень интересно, спасибо❤
Борис ,здравствуйте ,вы не могли бы рассказать почему в большинстве олимпиадных задач по геометрии дается задание что -либо доказать, почему они сложнее чем найти ,можно увидеть видеоролики по топу самых сложных задач из элементарной геометрии? Как доказывать какие -либо факты,и как понять что вот ,мы доказали. Можно узнать в чем сложность задач по геометрии международного уровня ?Если не трудно будет, расскажите про это :)
Борис Викторович, здравствуйте!
Вы сказали в ролике, что число I меньше числа n = pq. Далее, применили Th Эйлера:
I^N сравнимо с 1 по модулю n, где N = (p -1)(q - 1) - значение функции Эйлера для числа n. Но, ведь теорема Эйлера доказывается при обязательном условии, что числа I и n взаимно просты, т.е НОД (I, n) = 1.
Если тот, кто шифрует информацию берёт I < n, то это не означает, что его I не может оказаться числом кратным р или q (пусть эти кратные меньше, чем n = pq, т.е. требование I < pq - выполнено). Тем более, что p и q это огромные числа и таких кратных (kp < qp и jq < pq), тем больше, чем больше сами числа р и q.
Если случайно окажется, что шифровальщик взял, например, I = kp < qр, тогда получаем: НОД(I, n) = р > 1.
Но, тогда разве мы можем воспользоваться теоремой Эйлера? Ведь, она верна только для тех чисел I, у которых НОД (I, n) = 1.
А, тот кто шифрует информацию (беря I < n) знает n, но не знает p и q.
P.S. Правда, я рассмотрел сейчас несколько примеров, - брал маленькие простые: р < q, и затем брал I = ip < qp = n (i - натуральное), ну и, соответственно, брал натуральные числа а и b, такие что аb делится на (р -1)(q - 1) с остатком 1.
Затем находил остаток Т от деления (ip)^a на n. Потом, непосредственно (не используя теорему Эйлера), находил остаток от деления Т^b на n и получал, что этот остаток равен I = ip.
Нужно попробовать доказать в общем виде, что в том случае, когда, например,
I = ip < qp (т.е. НОД(I, n) = р > 1), тем не менее, всё равно Т^b сравнимо с I по модулю n.
prnt.sc/ve0j7c
@@trushinbv . Ух, ты! Красиво. Спасибо!
@@trushinbv , я заменю, с Вашего позволения, букву Гамма (в левой колонке скриншота) на x (просто Гамма у меня нет на клавиатуре).
У меня ещё, тогда, остался вопросик:
- почему x^(Nk + 1) = x (mod n). Но, попробую сам разобраться с этим!
@@trushinbv Ну, похоже, разобрался с гаммой (что в левой колонке скриншота) в степени (Nk + 1)
Там же фокус в том, что само это число гамма (обозначим его: х) тоже может быть кратным р. У нас: I = хр < qp, т.е. имеем ограничение: х < q < n. Если х взаимно прост с n = pq, то НОД(х, n) = 1. Тогда, применив теорему Эйлера получим: х^(Nk + 1) = x(х^N)^k =х (mod n).
Но, ведь (при х < q < n), ничего не мешает числу х быть, как упомянуто выше, кратным р (например, при p^2 < q < n и т.д). Таким образом, пусть х = mр,
тогда х^(Nk + 1) = (mp)^(Nk + 1) = m^(Nk + 1)*р^(Nk + 1) = pm^(Nk + 1) по модулю n (доказательство, что р^(Nk + 1) = р (mod p), см скриншот БВ). Ну, ясно, что дальше смотрим на m (оно взаимно просто с n или нет) и, как бы методом спуска, по индукции, идём вниз к некоторому последующему m, взаимно простому с n.
Но, можно и по другому. Если I = хр < n (х < q), мы можем разложить I на простые множители и все они будут (лишь, возможно, за исключением некоторой степени числа р) взаимно просты с n. Тогда, обозначим произведение этих простых множителей (взаимно простых с n), как Y (следовательно, Y тоже взаимно просто с n) и число I = хр, запишем, как
I = Yр^c (I < n). Тогда:
I^(Nk + 1) = (Yр^c)^(Nk + 1) = Y^(Nk + 1)*(p^(Nk + 1))^c =
= Y^(Nk + 1)*р^c по модулю р. Но Y и n взаимно просты, тогда применив Теорему Эйлера, получим: Y^(Nk + 1) = Y (mod n). И окончательно:
I^(Nk + 1) = Yр^c (mod n), а это, см выше, и есть I = Yр^c.
@@IgorGusev28
Мне казалось, что я ответил, но сейчас обнаружил, что моего ответа нет (
Все проще:
- мы поняли, что p^(Nk+1)=p,
- аналогично, q^(Nk+1)=q,
- если с взаимно просто с n, то с^(Nk+1)=с.
А любое число I можно представить как c⋅p^k⋅q^m.
Этот алгоритм называется RSA, кому интересно
Наберите в поисковике: Закон расположения простых чисел найден.
Какое же годное видео и формат
15:18 - нужно разложить фи (n) на множители. не совсем понятно. ведь у числа n всего два множителя-простые p и q? нет? кажется можно создать массив возможных n, и соответствующих ему p и q- и отсюда сразу же найти фи (n)=(p-1)(q-1)? нет?
Поэтому число n берётся очень большое: сотни знаков. Словарь таких простых чисел с текущими компьютерами пока что невозможно создать
@@super_street_fighter о. Спасибо за ответ. Эту тему вообще забыл.Сейчас подбухнутый. Завтра попробую понять :)
Ответ на задачку: А3, Левый подъезд, 1 этаж.
На видео Борис не спроста показал края домиков для понимания левости или правости подъездов)
Такая атмосфера и ваш достаточно низкий голос... помогли мне заснуть на середине видео) спасибо большое, давно так не высыпалась)
На самом деле, чтобы расшифровать одноалфавитный шифр замены, достаточно в среднем 5(!) слов. С помощью частотного анализа можно сопоставить символы с самыми частыми буквами типо а,о,с,к и пр. При владении языка, на котором написано сообщение остальные слова уже отгадываются без труда
Я знаю, что применяли такой способ шифрования. Одна буква обозначалась несколькими символами. Символы разные, а буква одна. И ещё, вставлялись ничего не значащие символы. Их надо было просто пропустить. Это применялось не только для букв, но и для знаков препинания, цифр, пробелов между словами. Если одна буква могла обозначается достаточно большим количеством разных символов, и вставлялось достаточно большое количество ничего не значащих символов, правда длина текста увеличивалась раз в пять- шесть, расшифровать текст было практически невозможно.
А3, правый подъезд, первый этаж
Решение:
1)
От буквы зависит первая цифра номера (в алфавитном порядке)
A - 1
B - 2
C - 3
(D - 4)
E - 5
2)
Вторая цифра номера означает этаж
3)
На первом этаже в первом подъезде дома A1 должны быть комнаты 01-02 в одном подъезде и 03-04 в другом.
05-06 это дом A2 и по видео видно что это левый подъезд
Тогда 07-08 это дом А2 правый подъезд, далее:
09-10 лп A3
11-12 правый подъезд A3
Значит 1111 это правый подъезд A3
Извиняюсь за немного сумбурное решение, но надеюсь оно понятно.
Как же круто!
Имею генератор случайных чисел (ГСЧ). Сначала прокручиваю его, к примеру, на N=1000540001 оборотов (это ключ), потом, получив случ.число, сдвигаю букву шифруемого текста (по какому-то алфавиту) на это число позиций. Посылаю получателю. Дальше всё повторяется для всех букв текста. Получатель имеет такой же ГСЧ. Запускает его и сначала прокручивает его на N оборотов, дальше идёт расшифровка способом движения назад по алфавиту. Просто и почти недоступно взлому и расшифровке.
*) Разумеется, имеется в виду генератор псевдослучайных чисел.
Это Энигма 😊
Занимался теорией чисел с 9го класса (сейчас в 11), очень интересно было увидеть подобное применение
Наберите в поисковике: Закон расположения простых чисел найден.
@@АлександрВолков-е1р1и и что? Какое отношение это имеет к разложению больших чисел на простые множители?
Эх, как жаль, что я не узнал об этом в Школе.. Математике не хватает практических применений в школьной программе. Нас Этому просто забывают учить
{y=(3-ax)/b,b=(3-ax)²/(7-ax²),a=-1/(3x³+2x),(3x²+2)³(21x²+x+14)³=(9x ²+7)²(x³+126x²+84);x=-0,02±0,51i;-0,2±0,90i;-0,01±0,88i;0,0026±0,82i;0,0064±0,87i;0,16±0,89i a=(±154i+1 1)/(121+154²);.. b=(3+(±0,0065i+4, 6*10-⁴)(0,02-+0,51i))²/(7+(±0,0065i +4,6*10-⁴)(0,02-+0,51i)²),y=7, ax⁵+by⁵=(+0,0965i+4,6*10-⁴)(-0,02± 0,51i)⁵+3*7⁴=3*7⁴✓
Школьные преподы, зачастую, сами не знают где это всё нужно => не могут нормально объяснить => не преподают
Теория чисел конечно применяется в криптографии и не только в ней, но вообще-то её две тысячи лет развивали чисто из интереса. Те кто ей занимались даже гордились, что это чистая математика, которая не имеет практического применения, особенно военного.
А в криптографии её начали применять очень недавно, после второй мировой. Одним из первых это предложил Алан Тьюринг, который вместе с группой других британских математиков взломали немецкую шифровальную машину Энигма
A1l = 1301 ?
A1r = 1302 (1101-1102, 1201-1202)
A2l = 1303 (1103-1104, 1203-1204)
A2r = 1304 (1105-1106, 1205-1206)
A3l = 1305 (1107-1108, 1207-1208)
A3r = 1306 (1109-1110, 1209-1210)
A4l = 1307 (1111-1112, 1211-1212)
B4l = 2307 (2115-2116, 2215-2216)
C6r = 3312 (3123-3124, 3223-3224)
E5l = 5309 (5119-5120, 5219-5220)
Первая цифра в номере комнаты указывает на порядковый номер литеры домика в алфавите, вторая цифра указывает на этаж.
В каждом домике по 10 комнат.
В домике А1 левый подъезд скорее всего административный и не участвует в общей нумерации. На это еще указывает смещение нумерации комнат в домиках с литерой А.
Ответ: А4, левый подъезд, первый этаж.
с первым и вторым этажами понятно, но третий как-то подозрительно составлен. В доме А2 ожидаешь увидеть на третьем этаже 1303, в доме E5 5310, в доме B4 2308.
Ниче не понял но мне понравилось
Наберите в поисковике: Закон расположения простых чисел найден.
а3, правый подъезд, 1 этаж
Борис Викторович,спасибо вам за видео!
Интересует вопрос : планируются ли скидки на курсы в будущем учебном году? Интересует Физика и Математика.
Заранее спасибо за ответ.
Мы его даже пока продавать не начали )
Если будут скидки, то промокод появится в нижней части этого сайта -- trushinbv.ru
Борис Трушин
Спасибо за ответ!
@@trushinbv прямо алгоритм вижу по расшифровки замененных символов по сочетанию условий : длине слова ++ частота (вероятность) слова + частоте букв n-ой позиции
@@trushinbv да уж, опять темку степеней поднял, весь день маньячил, полтетради исписал, 2 алгоритма разложения на множители довел до ума, ну все равно идеала не получилось, степень раскладывать продолжил, точнее с остатками работал, там уже очевидно, что все упирается в единицу и из пару (двойку). Буду на английский сегодня нажимать, хоть не напрягает. Как ты подчеркнул в одном из видео, что некоторые задачи неделю нужно решать, если бы, некоторые годами(, а некоторые со злостью штурмом решаются
Можно так же доходчиво про биткоин? ))
Полно же роликов))
Каждая транзакция записывается в блокчейн. Новая запись это хэш всего, что было до этого (понятно, что считается он сложно). Поэтому задним числом ничего не поменять: придётся пересчитывать весь блокчейн, что нереально. За выполнение записей берут комиссию и получают премию - тот самый майнинг. Копии блокчейна есть у всех желающих. Там написано кто, когда, кому и сколько. Всё. Дальше технические детали. Номера кошельков, правила записи, ЭЦП, правила вычислений, арбитраж и т.д.
А что если закодировать другим способом. Например от 650 до 800 отвечает на букву А. От 801 до 1500 отвечает за пробел. От 1501 до 2000 означает точку. Если мы использовали цифру 650 то мы ее не можем использовать повторно . То есть мы использовали 650 потом на эту же букву используем 651, 652 и тд по очереди. 650 повторно не используем чтобы люди не смогли взломать частотным анализом. После того как мы использовали цифру 800 мы можем использовать цифру 650 и ток по кругу. Цифры не привязаны к языкам. 2001 до 4000 это ловушка. Они нужны чтобы отнять время взломщиков. Эти цифры не несут никакой ценности. Это как сундук с камнями. Камни для веса. И разбойники уходят с пустыми руками ведь сундуки были обманом. Как то так. Благодарю вас
Султан! Я над этим думал лет 45 назад. Но из-за этого шифровка будет длиннее. Буква в компьютере занимает 8 бит, то есть байт. Еще надо иметь несколко бит, которые показывают вариант кодирования этой буквы. Например, буква имеет такой код: 10011100. А после шифрования такой: 11011011 - этот код должен пойти в шифровку. Если добавить к этому коду 4 бита справа, то будеи меть возможность закодировать эту букву 16 вариантами: 000011011011 000111011011 001011011011 ... 111111011011. Но расшифровывать ее будут по байтам, то есть: 00001101 10110001 11011011 00101101 1011... Частотный анализ здесь работать не будет, но информация расширяется в 1,5 раза. Да и не мешало бы продумать в как перемешивать биты.
@@NordKavkaz-i2u я в компьютерном деле мало шарю. Вы уж меня простите
@@NordKavkaz-i2u почему не будет работать частотный анализ? Хороший криптографический алгоритм открыт для анализа. В данном случае мы будем знать диапазоны. То есть от 801 до 1500 какая то буква. Вот и можем использовать частотный анализ не на числа, а на диапазоны. Если же мы в качестве ключа, будем передавать сами диапазоны. То это ничем не отличается от невзламываемого шифра .
круто!
А3, правый подъезд, первый этаж и, наверное, правая комната.
Есть замок ,который гарантирует сложность открывания,есть вор, который знает как вскрыть замок,это обычное соревнование,не связанное с перебором всех комбинаций!!!!Вор легко может сломать механизм и замок,превращает в щеколду,т.е. задача сводится к двоичной задачи,целью математитики является свести задачу к двоичной системе!!!!!!
A3, второй подъезд, первый этаж
класс
A4, левый подъезд, первый этаж?
👍
А3, Первый этаж, правый подъезд...
Найдите легкий способ факторизовать 4096-битное число, опубликуйте - и вы обрушите мировую экономику :)
A3, правый подъезд , первый этаж
А3, левый подъезд, 1 этаж
А5 1 этаж левый подъезд
Комната №1111 находится в доме A3, Правый подъезд, 1й этаж.
Теперь ясно. В школе надо было учить математику, чтобы секретно общаться. Ну-с будем исправлять.
Ваня Днепров если у вас есть просторе число р (например 3), то для любого целого а (например 6), будет справедливо утверждение: а^(р-1) будет сравнимо с 1 по модулю р (в нашем случае 3). То есть остаток от деления а^(р-1) на р будет равен 1 ( Ето фориулировка в лектора.) Я предлагаю вам проверить будет ли справедливо ето утверждение..
это видео не о простых числах, а о шифрование.
да и это просто.
а смысла простых чисел я всё равно не понял.
A5, Первый этаж, правый подъезд?
Алгоритм RSA) основан на работе с группами Zn и Zn*
А7 1 этаж правый подъезд
А5, левый падик, первый этаж
БВ, вы не знаете почему, при описании алгоритма RSA, требуют, чтобы альфа была взаимно проста с функцией Эйлера и была меньшее ее? 10:03
А1, 1 этаж, левый подъезд.
A3, левый подъезд, первый этаж. Скорее всего это и есть комната Бориса Викторовича.
Мне кажется что сейчас уже есть технология разложения числа на простые множители быстро. Это майнинг криптовалюты и сотни ферм для етого. Если я не ошибаюсь, там заложен именно такой механизм. То есть скоро будут известны "все" пари простых чисел. Поправьте если я не прав...
Вам кажется. В майнинге хоть и называется "полезные вычислительные мощности" криптофермы ничего полезного не делают. Там идет простой подбор определнной хешсуммы от последней цепочки блокчейна.
Чёрная магия.
А4, левый подъезд, 1 этаж
Эх, только сам хотел запилить..
Увы, но малая теорема Ферма не является действенной для проверки простых чисел. Достоверно проверить на простоту числа может только тест Агравала-Каяла-Саксены.
Она, вроде, на это и не претендует )
@@trushinbv ну да, просто вы, я заметил, не акцентируете свое внимание на этом.
Но, увы, я не математик, а так, просто интересующийся.
Благодаря вам много интересного для себя узнал и понял на 4-м десятке лет.
Работаю в банковской сфере с достаточно умными и образованными людьми в технической сфере, но есть, на первый взгляд, простые факты, связанные с финансовыми рынками, которые никак пока не поддаются математическим объяснениям.
Хорошо с Теорией чисел разобрались, а для чего нужны параметры?
Ну как для чего, для того, чтобы развивать математическое мышление, решая задачи с ними, сами они не имеют большого смысла.
странно. Для промышленных целей проще обменяться шифроблокнотами (случайными последовательностями символов)и работать как Штирлиц. Просто и убойно. Да, тут нет открытого ключа ну и черт с ним.
1. как обменяться? что бы быть уверенным , шифроблокноты никто не перехватил. 2. Что делать если будет подозрение на компроментацию шифроблокнотов? 3. Что делать при рассинхронизации или провреждении шифроблокнотов? . да это действительно проще и главное более надежнее в случае 2х получателей. Но когда у тебя тыщы микросервисов работающих на сотнях серверов - гоняющие между собой петабайты не всегда полезноой инфы....
@@arxxximed Вот. Как сказал сократ -спрятать камень лучше всего среди похожих камней. Не хрен все шифровать свирепо для тыщ микросервисов-эти сервисы не особо и нужны.
1. Как обменяться? курьером с личным контактом,
2. Условный сигнал на запасной блокнот.
3. Запасной блокнот
@@barackobama2910 погодите. Вы ж сказали в промышленных целях. Это что? два три слова ?)). Ну и какие требования у промышленной передачи данных? 1. Целостность 2. Скорость. Блокноты как раз решают вопрос полного шифрования, исключая скорость и целостность. Нужно срочно передать за 3000 км секретные чертежи, но мы ждем курьера с блокнотом ключей)) А пока курьер приехал, оказалось что флешка курьера "размагнитилась" и пару тыщ цифр в ключах были заменены на случайные или вообще потеряны. Ну и главное , а как спрятать курьера? быть уверенным что его не завербуют по дороге, или еще хуже , он изначально сдает все блокноты?
@@arxxximed Как делал Эрих манштейн. Он слал курьера с секретным приказом а реальный приказ доставлял на словах доверенный унтер на которого никто бы не заподозрил. Так он несколько раз обвел за нос Ватутина.
Шифроблокнот присылается в виде порнокартинки на открытом для всех сайте соцсети. Просто получатель знает как найти картинку а шпионы не знают, а картинок в сети миллиарды.
Так же и штирлиц давал в газету объявление "бабушка Ильза здорова". Но только получатель знал что это означает. И никто не знает какое объявление и когда кодовое.
@@arxxximed И да. коррумпированный персонал вас все равно сдаст, поможет только квантовое шифрование и то не всегда.
Если это круто то я точно Дарт Вердер.
добью до 80 комента
Я так понял, проблеба расшифровки только том что не все устройства смогут производить математические операции с 600 значным числом, и все?
сейчас почти все устройства могут производить операции с 600 и больше значным числом. )) смотря какие операции, проблема математической расшифровки всегда в ассиметричности некоторых математических функций. возьмите простое большое число, и возведите в степень этого же числа. Это просто. и компьютер справится с этим очень быстро. А если же попробовать наоборот? Разложить большое число на простые множители? то кроме алгаритма перебора пока ничего не известно..
th-cam.com/video/Oc4QSFxTuXQ/w-d-xo.html
@@arxxximed А в чем тогда сложность шифрования информации?
@@NickProkhorenko по моему в нормальном алгоритме шифрования не должно быть сложности шифрования, должна быть сложность в дешифровке )))
А про энигму не рассказал!)
Не правильная крипто загадка .По количеству и форме иголок вычислить вид сосны , её ареал распространения .И конечно дать правильный ответ - где сейчас аФтар находиться : Крым или "Сочи".?
Блин. С моей дырявой памятью я не смог запомнить с 1-го раза что есть n m beta и т.д.
"Какого **********!!!" Нигде нет примера с числами(
Ну это же один из разделов математике, которая называется комбинаторикой?
комбинаторикой называется совершенно другой раздел математики
Извиняюсь за свое невежество. Услышал про теорему Ферма и факториал - сразу подумал про комбинаторику, но и конечно это слабая логика :D
Сложновато Рассказал :) Не хотел бы Я пытаться понять Алгоритм Шора в Изложении Этого Аффтара :)
Квантовый компьютер способен числа, состоящие из 1000 цифр, разложить на простые множители за пару минут
осталось построить квантовый компьютер
Александр Марков следите за новостями, уже строят квантовые компьютеры из нескольких десятков кубитов
Есть 2 проблемы:1) кватновые компьютеры на столько кубит узконаправленны и решают другие задачи, 2) многофункциональные квантовые компьютеры почти на 0 уровне развития. Но вообще да, эта технология - конец для нынешней криптографии
Василий Понаморев Нет, не конец. Разработан метод Брассара-Беннета передачи совершенно секретных сообщений по фотонной линии. Там применяются поляризованные фотоны и принцип неопределённости. Короче, это метод одноразовых блокнотов, при этом проблему распределения ключей решают с помощью квантовой физики.
Интересная инфа, но кто трясёт камеру? Зачем..у меня уже нервный тик от этого😢
Как расшифровать "ЪУЪ"?
На самом деле даже обидно, что такая мутная для меня область математики настолько применима сегодня. То есть, уже не получится рационализовать своё нежелание ботать тем, что "оно нигде не применяется".
Кстати, если хотите изучать теорию чисел - можете пойти на мехмат МГУ. У нас в первом семестре есть предмет Элементы теории чисел, а на факультете существует Кафедра теории чисел, которая принимает студентов.
94 русский, уеее
Slowpokan 89(((
Кто то решил задачу?
Какая мерзкая жидкая бородка(
Меня одну бесит эта бородка?
Возможно, стоит это обсудить со своим психологом )
Какой все таки странный человек. Еще не научился однозначно понимать символьную передачу информации, а уже пытается её шифровать...