C rsa: Компактная реализация RSA для встраиваемых применений / Хабр

Содержание

Хватит использовать RSA / Блог компании Virgil Security, Inc. / Хабр

Привет, %username%!

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

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

По какой-то причине люди до сих пор считают RSA хорошим алгоритмом. Но на самом деле, простор для выстрела в ногу при реализации RSA чрезвычайно огромен. Слабые параметры проверить трудно, если не невозможно. А слабая производительность алгоритма побуждает разработчиков использовать рискованные способы её повысить.

Хуже того, атаки типа padding oracle, которые изобрели более 20 лет назад, актуальны и сегодня.

Даже если в теории и возможно имплементировать RSA корректно, на практике такой «подвиг» совершить почти невозможно. И уязвимости, постоянно возникающие уже на протяжении десятилетий, это только подтверждают.

Пару слов об алгоритме RSA

Если знаете, как работает RSA, эту часть можно пропустить.

RSA — криптосистема с открытым ключом, у которой есть два применения.

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

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

Оба алгоритма отличаются незначительными деталями, поэтому будем их называть просто RSA.

Чтобы начать работать с RSA, Алисе нужно выбрать два простых числа p и q, которые вместе образуют группу чисел по модулю N = pq. Потом Алисе нужно выбрать открытую экспоненту e и секретную d такие, что . По сути, e и d должны быть взаимно просты.

Как только эти параметры будут выбраны, Боб может послать Алисе сообщение M, вычислив . Алиса может затем расшифровать сообщение, вычислив .

Цифровая подпись происходит ровно наоборот. Если Алиса хочет подписать сообщение, она вычисляет подпись , которую Боб может проверить, убедившись, что сообщение

Вот как бы и всё, это основная идея. К Padding oracles мы вернёмся попозже, а пока давайте посмотрим что можно сделать если параметры RSA выбраны неверно.

Начало конца

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

Генерация простых чисел

Безопасность RSA основана на том факте, что имея большое число N, являющееся произведением двух простых чисел p и q, разложение N на простые множители, не зная p и q сделать трудно. Разработчики несут ответственность за выбор простых чисел, составляющих модуль RSA. Этот процесс чрезвычайно медленный по сравнению с генерацией ключей для других криптографических протоколов, где достаточно просто выбрать несколько случайных байтов. Поэтому, вместо того чтобы генерировать действительно случайное простое число, разработчики часто пытаются создавать числа определенной формы. Это почти всегда плохо кончается. Существует много способов выбора простых чисел таким образом, чтобы факторинг N был простым. Например, p и q должны быть глобально уникальными. Если p или q когда-либо повторно используются в других модулях RSA, то оба множителя можно легко вычислить с помощью алгоритма GCD. Плохие генераторы случайных чисел делают этот сценарий довольно вероятным, и исследования показали, что примерно 1% трафика TLS в 2012 году было подвержено такой атаке.

Более того, p и q должны быть выбраны независимо друг от друга. Если p и q совместно используют приблизительно половину своих старших битов, то N может быть вычислено с использованием метода Ферма. На самом деле, даже выбор алгоритма тестирования простоты может иметь последствия для безопасности. Пожалуй, самая широко разрекламированная атака — это уязвимость ROCA в RSALib, которая затронула многие смарт-карты, модули доверенных платформ и даже ключи Yubikey. Здесь при генерации ключей используются только простые числа определенной формы для ускорения вычислений. Простые числа, сгенерированные таким образом, тривиально обнаружить, используя хитрые приемы теории чисел. Как только слабая система была распознана, специальные алгебраические свойства простых чисел позволяют злоумышленнику использовать метод Копперсмита для разложения N.

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

Секретная экспонента d

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

Вы скажете, что обычно при инициализации RSA вы сначала генерируете модуль, используете фиксированную открытую экспоненту, а затем выбираете секретную?

Да, это предотвращает атаки с маленькой секретной экспонентой, если вы всегда используете одну из рекомендуемых открытых экспонент e.

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

Открытая экспонента e

Как и в случае c секретной экспонентой, разработчики хотят использовать небольшие открытые экспоненты, чтобы сэкономить на шифровании и проверке подписей. Обычно в этом контексте используются простые числа Ферма, в частности e = 3, 17 и 65537.

Несмотря на то, что криптографы рекомендуют использовать 65537, разработчики часто выбирают e = 3, что приводит к множеству уязвимостей в криптосистеме RSA.

(Тут разработчики использовали e = 1, который на самом деле не шифрует открытый текст вообще.)

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

Например, атака Франклина-Рейтера позволяет злоумышленнику дешифровать два сообщения, которые связаны известным, фиксированным расстоянием. Другими словами, предположим, что Алиса посылает Бобу только «купить» или «продать». Эти сообщения будут связаны известным значением и позволят злоумышленнику определить, какие из них означают «купить», а какие «продать», не расшифровывая сообщения. Некоторые атаки с маленькой e могут даже привести к восстановлению ключа.

Если открытая экспонента маленькая (не только 3), злоумышленник, который знает несколько бит секретного ключа, может восстановить оставшиеся биты и сломать криптосистему. Хотя многие из этих e = 3-атак на RSA можно пофиксить выравниванием (padding), разработчики, которые сами реализуют RSA, чрезвычайно часто забывают его использовать.

Подписи RSA также уязвимы для маленьких публичных экспонент. В 2006 году Блейхенбахер обнаружил атаку, которая позволяет злоумышленникам подделывать произвольные подписи во многих реализациях RSA, в том числе используемых в Firefox и Chrome. Это означает, что любой сертификат TLS из уязвимой реализации может быть подделан. Эта атака использует тот факт, что многие библиотеки используют небольшую публичную экспоненту и не делают простую проверку выравнивания при обработке подписей RSA. Атака Блейхенбахера на подпись настолько проста, что включена во многие упражнения на курсах криптографии.

Выбор параметров — трудная задача

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

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

Padding Oracle атаки

Как мы уже выяснили выше, простое использование RSA «из коробки» не совсем работает. Например, схема RSA, изложенная во введении, будет создавать идентичные шифротексты, если один и тот же открытый текст когда-либо шифровался более одного раза. Это проблема, потому что это позволит злоумышленнику узнать содержание сообщения из контекста, не имея возможности расшифровать его. Вот почему нам нужно выравнивать сообщения несколькими случайными байтами. К сожалению, наиболее широко используемая схема выравнивания, PKCS # 1 v1.5, часто уязвима к так называемой атаке padding oracle.

Первоначальная атака на PKCS # 1 v1.5 была обнаружена еще в 1998 году Даниэлем Блейханбахером. Несмотря на то, что ей более 20 лет, сегодня она продолжает быть актуальной для многих систем. Современные версии этой атаки часто включают в себя дополнительный оракул, немного более сложный, чем тот, который первоначально описал Блейханбахер, например, время отклика сервера или выполнение какого-либо понижения версии протокола в TLS. Одним особенно шокирующим примером была атака ROBOT, которая была настолько ужасной, что команда исследователей смогла подписать сообщения секретными ключами Facebook и PayPal. Некоторые могут возразить, что это на самом деле не вина RSA — основная математика в порядке, люди просто испортили важный стандарт несколько десятилетий назад. Дело в том, что у нас уже тогда, с 1998 года была стандартная схема выравнивания с строгим доказательством безопасности, OAEP. Но почти никто не использует ее. Даже когда это происходит, общеизвестно, что OAEP сложно реализовать, и он часто уязвим к атаке Мангера, которая является еще одной атакой оракула, которую можно использовать для восстановления открытого текста.

Фундаментальная проблема здесь заключается в том, что выравнивание необходимо при использовании RSA, и эта дополнительная сложность открывает большой простор для атак на криптосистему. Тот факт, что один бит информации, «правильно ли было выровнено сообщение», может оказать настолько большое влияние на безопасность, что делает разработку защищенных библиотек практически невозможной. TLS 1.3 больше не поддерживает RSA, поэтому мы можем ожидать, что в будущем будет меньше таких атак.

Но пока разработчики будут продолжать использовать RSA в своих собственных приложениях, Padding Oracle атаки будут продолжать происходить.

Что делать?

Люди часто предпочитают использовать RSA, потому что они считают, что это концептуально проще, чем запутанный протокол DSA или криптография с эллиптической кривой (ECC). Но хотя RSA интуитивно понятнее, ему очень не хватает защиты от дурака.

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

Во-вторых, любое согласование ключей на основе алгоритма Диффи-Хеллмана или схема подписи (включая варианты эллиптической кривой) не требуют выравнивания и, следовательно, полностью устойчивы к атакам Padding Oracle. Это серьезная победа, учитывая, что у RSA очень длинный послужной список попыток избежать этого класса уязвимостей.

Мы рекомендуем использовать Curve25519 для обмена ключами и ed25519 для цифровых подписей. Шифрование должно выполняться с использованием протокола ECIES, который сочетает в себе обмен ключами ECC с алгоритмом симметричного шифрования. Curve25519 была разработана чтобы полностью предотвратить классы атак, которые могут случиться с другими кривыми, а еще она очень быстрая. Более того, она реализована во множестве библиотек, например libsodium, который снабжен легкой для чтения документацией и доступен для большинства языков.

Хватит использовать RSA. Серьезно.

(Twilio до сих пор использует RSA ключи)

(Travis CI до сих пор использует 1024 битные ключи и не даёт их заменить)

RSA был важной вехой в развитии безопасных коммуникаций, но последние два десятилетия криптографических исследований сделали его устаревшим. Алгоритмы на эллиптических кривых как для обмена ключами, так и для цифровых подписей были стандартизированы еще в 2005 году и с тех пор были интегрированы в интуитивно понятные и устойчивые к неправильному использованию библиотеки, такие как libsodium. Тот факт, что RSA все еще широко используется в наши дни, указывает как на ошибку со стороны криптографов из-за неадекватного описания рисков, присущих RSA, так и со стороны разработчиков, переоценивающих свои способности успешно развертывать его. Security сообщество должно начать думать об этом как о стадной проблеме — хоть некоторые из нас и могут быть в состоянии ориентироваться в чрезвычайно опасном процессе настройки или реализации RSA, исключения дают понять разработчикам, что в некотором роде RSA еще актуален. Несмотря на множество предостережений и предупреждений на StackExchange и GitHub README, очень немногие люди верят, что именно они испортят RSA, и поэтому они продолжают поступать безрассудно. В конечном счете ваши пользователи будут платить за это. Вот почему мы все должны согласиться с тем, что использование RSA в 2019 году совершенно неприемлемо. Без исключений.

Оригинал статьи на английском.

VirgilSecurity, Inc. разрабатывает open source developer friendly SDK и сервисы для защиты данных. Мы позволяем разработчикам использовать существующие алгоритмы с минимальным риском для безопасности.

P.S. рекоммендую так же почитать о встраивании бекдора в публичный ключ RSA.

Шифрование RSA для первокурсников / Хабр

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

В этой статье я решаю на языке MIT Scheme задачу шифрования и дешифрования методом RSA [1]. По ряду причин, которые рассматриваются в статье, реализация не может использоваться для криптографической защиты информации.

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

Первый этап генерации ключей — случайный выбор двух достаточно больших простых чисел p и q. Натуральное число x называется простым, если у него есть ровно два различных делителя: 1 и x. Все другие делители числа располагаются на отрезке от 2 до квадратного корня из x, однако достаточно проверять на кратность только простые делители, принадлежащие этому отрезку.

(define (Primes n)
  (define (prime? n primes)
    (define (iter divisors)
      (or (null? divisors)
          (let ([divisor (car divisors)])
               (or (> (* divisor divisor) n)
                   (and (< 0 (remainder n (car divisors))) (iter (cdr divisors))))))
      )
    (iter primes)
    )
  (define (iter primes i candidate)
    (cond 
      ((= i n) primes)
      ((prime? candidate (reverse primes)) (iter (cons candidate primes) (+ i 1) (+ candidate 1)))
      (else (iter primes i (+ candidate 1)))
      )
    )
  (iter '() 0 2)
  )
(define primes (Primes 100))
(define p (car primes))
(define q (car (drop 10 primes)))

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

(define n (* p q))

Для вычисления вторых элементов открытого и закрытого ключей используется величина fi, равная функции Эйлера [3], вычисленной на n. Функция Эйлера от x равна количеству натуральных чисел, не больших x и взаимно простых с ним. Для n это количество будет равно произведению p-1 и q-1.

(define fi (* (- p 1) (- q 1)))

Вторым элементом открытого ключа выбирается случайное число e в диапазоне от 1 до fi, являющееся взаимно простым с fi. то есть таким, что наибольшим общим делителем чисел является 1.

(define (CoprimesLess n)
  (define (iter accumulator candidate)
    (cond
      ((= 1 candidate) accumulator)
      ((= 1 (gcd n candidate)) (iter (cons candidate accumulator) (- candidate 1)))
      (else (iter accumulator (- candidate 1)))
      )
    )
  (iter '() (- n 1))
  )
(define e (car (drop 5 (CoprimesLess fi))))

Для поиска наибольшего общего делителя можно использовать алгоритм Евклида [4].

Одним из объектов, изучаемых теорией чисел, является кольцо вычетов [5]. Кольцо вычетов по модулю k — это целые числа от 0 до k-1 и операции сложения и умножения на нём. Сложение в кольце вычетов (a + b mod k) отличается от сложения в группе целых чисел тем, что если результат сложения становится больше k, из него вычитается k, в результате чего этот результат снова оказывается в кольце. Интуитивно, кольцо получается из отрезка соединением его концов.

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

a + (b + c mod k) mod k = (a + b mod k) + c mod k

a * (b * c mod k) mod k = (a * b mod k) * c mod k

Вторым элементом открытого ключа должно быть число d такое, что его произведение с e в кольце вычетов по модулю n является 1, то есть мультипликативно обратный элемент. Привожу алгоритм поиска такого элемента при помощи расширенного алгоритма Евклида [6].

(define (MultInverseModN a n)
  (define (iter a-prev a r-prev r)
    (if (>= 1 r) a (let* ([r-next (remainder r-prev r)]
                          [q (quotient r-prev r)]
                          [a-next (- a-prev (* q a))])
                         (iter a a-next r r-next)))
    )
  (let ([result (iter 0 1 n a)]) (if (< 0 result) result (+ n result)))
)
(define d (MultInverseModN e fi))

При помощи алгоритма RSA можно шифровать сообщения, представленные серией чисел M в диапазоне от 0 до n-1. Шифрование состоит в возведении M в степень e в кольце вычетов по модулю n, дешифрование — в степень d. Благодаря тому, что умножение является ассоциативным, мы можем возводить в степень x за log(x) операций [7].

(define (PowerModN a b n)
  (define (iter accumulator multiplicator power)
    (if
      (= power 0)
      accumulator
      (let
          ((new_accumulator (if (even? power) accumulator (remainder (* accumulator multiplicator) n))))
          (iter new_accumulator (* multiplicator multiplicator) (quotient power 2))
        )
      )
    )
  (iter 1 a b)
  )

В моём примере открытый ключ представляет собой пару (250483 31), закрытый — пару (250483 32191). Зашифрованное сообщение 123456 равно 133240.

en.wikipedia.org/wiki/RSA

en.wikipedia.org/wiki/Integer_factorization

en.wikipedia.org/wiki/Euler%27s_totient_function

en.wikipedia.org/wiki/Euclidean_algorithm

en.wikipedia.org/wiki/Modular_arithmetic

en.wikipedia.org/wiki/Extended_Euclidean_algorithm

en.wikipedia.org/wiki/Exponentiation_by_squaring

RSA-шифрование на пальцах

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

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

Итак. Допустим, я хочу получить от вас некие данные.
Мы с вам не хотим, чтобы эти данные узнал кто-то,
кроме нас. И у нас нет никакой уверенности в надёжности
канала передачи данных. Приступим.

Шаг первый. Подготовка ключей

Я должен
проделать предварительные действия: сгенерировать
публичный и приватный ключ.

Выбираю два простых числа. Пусть это будет
p=3 и q=7.
Вычисляем модуль — произведение наших p и q: n=p×q=3×7=21.
Вычисляем функцию Эйлера: φ=(p-1)×(q-1)=2×6=12.
Выбираем число e, отвечающее следующим критериям:
(i) оно должно быть простое,
(ii) оно должно быть меньше φ — остаются варианты: 3, 5, 7, 11,
(iii) оно должно быть взаимно простое с φ; остаются варианты 5, 7, 11.
Выберем e=5. Это, так называемая, открытая экспонента.

Теперь пара чисел {e, n} — это мой открытый ключ. Я отправляю его
вам, чтобы вы зашифровали своё сообщение. Но для меня это ещё не всё.
Я должен получить закрытый ключ.

Мне нужно вычислить число d, обратное е по модулю φ. То есть
остаток от деления по модулю φ произведения d×e должен быть
равен 1. Запишем это в обозначениях, принятых во многих языках
программирования: (d×е)%φ=1. Или (d×5)%12=1. d может быть
равно 5 ((5×5)%12=25%12=1), но чтобы оно не путалось с e
в дальнейшем повествовании,
давайте возьмём его равным 17. Можете проверить сами, что
(17×5)%12 действительно равно 1 (17×5-12×7=1). Итак d=17.
Пара {d, n} — это секретный ключ, его я оставляю у себя. Его
нельзя сообщать никому. Только обладатель секретного
ключа может расшифровать то, что было зашифровано открытым ключом.

Шаг второй. Шифрование

Теперь пришла ваша очередь шифровать ваше сообщение.
Допустим, ваше сообщение это число 19. Обозначим его
P=19. Кроме него у вас уже есть мой открытый ключ:
{e, n} = {5, 21}. Шифрование выполняется по следующему
алгоритму:

Возводите ваше сообщение в степень e по модулю n.
То есть, вычисляете 19 в степени 5 (2476099) и берёте
остаток от деления на 21. Получается 10 — это ваши закодированные данные.

Строго говоря, вам вовсе незачем вычислять огромное число
«19 в степени 5». При каждом умножении достаточно вычислять
не полное произведение, а только остаток от деления на 21.
Но это уже детали реализации вычислений, давайте не будем
в них углубляться.

Полученные данные E=10, вы отправляете мне.

Здесь надо заметить, что сообщение P=19 не должно быть больше
n=21. иначе ничего не получится.

Шаг третий. Расшифровка

Я получил ваши данные (E=10), и у меня имеется закрытый ключ
{d, n} = {17, 21}.

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

Начинаем раскодировать:

Я делаю операцию, очень похожую на вашу, но вместо e использую d.
Возвожу E в степень d: получаю 10 в степень 17 (позвольте, я не
буду писать единичку с семнадцатью нулями). Вычисляю остаток от деления
на 21 и получаю 19 — ваше сообщение.

Заметьте, никто, кроме меня (даже вы!) не может расшифровать ваше сообщение
(E=10), так как ни у кого нет закрытого ключа.

В чём гарантия надёжности шифрования

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

Постараюсь это показать на примере. Давайте разложим на множители число 360:

сразу ясно. что оно делится на два (получили 2)
оставшееся 180 тоже, очевидно чётное (ещё 2)
90 — тоже чётное (ещё двойка)
45 не делится на 2, но следующая же попытка оказывается успешной — оно делится на три (получили 3)
15 тоже делится на 3
5 — простое.

Мы на каждом шагу, практически без перебора, получали всё новые и
новые множители, легко получив полное разложение 360=2×2×2×3×3×5

Давайте теперь возьмём число 361. Тут нам придётся помучиться.

оно не чётное
три — нет, не делится
пять (допустим, мы поступаем умно и перебираем только простые числа, хотя, на практике, поиск больших простых чисел, сам по себе, является сложной задачей) — не подходит
семь? — нет.
…
и только 19 даст нам ответ: 361=19×19.

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

А как это всё работает на практике?

Многие читатели спрашивают, как всё это применяется на
практике. Давайте рассмотрим чуть более приближенный
к жизни пример. Зашифруем и расшифруем слово «КРОТ»,
предложенное одним из читателей. А заодно, бегло
рассмотрим, какие проблемы при этом встречаются и
как они решаются.

Сперва сгенерируем ключи с чуть бо́льшими числами.
Они не так наглядны, но позволят нам шифровать не только
числа от нуля до 20.

Оттолкнёмся от пары простых чисел {p, q} = {17, 19}.
Пусть наш открытый ключ будет {e, n} = {5, 323}, а
закрытый {d, n} = {173, 323}.

Мы готовы к шифрованию. Переведём наше слово в цифровое
представление. Мы можем взять просто номера букв в алфавите.
У нас получится последовательность чисел: 11, 17, 15, 19.

Мы можем зашифровать каждое из этих чисел открытым
ключом {e, n} = {5, 323} и получить
шифровку 197, 272, 2, 304. Эти числа можно передать
получателю, обладающему закрытым ключом {d, n} = {173, 323}
и он всё расшифрует.

Немного о сложностях

На самом деле, изложенный способ шифрования очень слаб и никогда
не используется. Причина проста — шифрование по буквам.
Одна и та же буква будет шифроваться одним и тем же числом.
Если злоумышленник перехватит достаточно большое
сообщение, он сможет догадаться о его содержимом.
Сперва он обратит внимание на частые коды пробелов
и разделит шифровку на слова. Потом он заметит однобуквенные
слова и догадается, как кодируются буквы «a», «и», «o», «в», «к»…
Путём недолгого перебора, он вычислит дополнительные буквы
по коротким словам, типа «но», «не», «по». И по более длинным
словам без труда восстановит все оставшиеся буквы.

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

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

Упрощённо, это выглядит так. Перед шифрованием, мы применяем
к сообщению правило: b := (b + a) % n. Где a — предыдущая
часть сообщения, а b — следующая. То есть наше сообщение
(11, 17, 15, 19) изменяется. 11 остаётся без изменений.
17 превращается в (11 + 17) % 323 = 28. 15 становится
(15 + 28) % 323 = 43. A 19 превращается в 62.

Последовательность (11, 28, 43, 62) получается
«запутанной». Все буквы в ней как бы перемешаны, в том
смысле, что на каждый код влияет не одна буква, а все
предыдущие.

Тот, кто получит ваше сообщение, должен будет
проделать обратную операцию, со знаком «минус»:
b := (b - a) % n. И только тогда он получит коды
букв.

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

То есть мы можем добавить случайное число в начало
и получить (299, 11, 17, 15, 19). После перемешивания
получится: 299, 310, 4, 19, 38. После шифрования
уже невозможно будет догадаться где была какая буква.

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

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

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

Отправить

RSA-шифрование: как работает «старый» алгоритм

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

Что представляет собой алгоритм?

Дата создания алгоритма RSA 1977 год. Аббревиатура придумана на основе фамилий разработчиков: R – Ривест, S – Шамир, A – Адлеман. Первый буквы и стали являться наименованием для шифрования и технологии в целом.

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

Шифрование

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

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

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

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

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

Цифровая подпись

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

Благодаря такой основе системе, подпись конфиденциальна. Вся содержащаяся информация сторонах надежно защищена.

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

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

Скорость работы

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

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

k² – процедуры с публичным ключом;
k³ – процедуры с приватным ключом;
k⁴ – для создания шифров.

Для ускорения проведения процедур на основе RSA постоянно применяются новые разработки. В качестве таковой мог стать способ «быстрого умножения», который позволял уменьшить число требуемых шагов для успешного и безопасного выполнения операции. БПФ (FFT) не прижилось, ведь для реализации требуется сложное ПО, а для быстрой работы понадобится сделать размер ключей идентичным.

Важно! Сегодня алгоритм RSA проигрывает в скорости большинству альтернативных способов блокового шифрования. Так DES минимум в сто раз быстрее при аппаратной реализации.

Как взламывают алгоритм RSA?

RSA – это изученный метод шифрования, который можно взломать несколькими способами. Самым эффективным является поиск закрытого ключа, который позволяет открыть информацию из открытого ключа. Позволяет получать всю информацию, которая была зашифрованной, также внедряться в код подписи, подделывая ее. Для проведения атаки необходимо найти сомножители общего модуля n – p и q. Благодаря данным p, q, e, хакер может без проблем получить частный показатель d. Основная трудность метода – поиск сомножителей. В основе безопасности лежит схема определения множителей, что позволяет создать задачу без эффективных вариантов решения.

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

Следующая возможность взлома заключается в поиске способа определения корня степени e из mod n. Если злоумышленник получит корень из уравнения C = M^e, то он получает доступ к зашифрованным сообщениям и возможность подделки подписи без знания приватного ключа. Сегодня не получается узнать схему, благодаря которой алгоритм взламывается подобным способом.

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

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

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

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

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

Что собой представляют «устойчивые числа»?

Для защиты шифрования должны использоваться устойчивые числа p и q. Они необходимы для выявления свойств, затрудняющих получение множителей. Одним из таких являются главные делители: p – 1 и p + 1. Это позволяет создать защиту от определения множителей различными методами, которые можно применять только в отношении небольших делителей. Использование устойчивых чисел даже закреплено в правилах некоторых стандартов, например, ANSI X9.31.

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

Важно! Если будут разработаны дополнительные способы факторинга, то в RSA можно будет увеличить количество символов в числе для усложнения задачи.

Множество простых чисел

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

Интересно! Ключ длиной 512 битов включает в себя 10¹⁵⁰ возможных значений.

Как это работает?

В реальности защищенная передача сообщений возможна при использовании двух криптосистем: RSA и DES. Алгоритм процесса:

Пользователь «А» отправляет сообщение пользователю «Б».
Сперва сообщение шифруется по алгоритму DES.
Ключ DES шифруется по алгоритму RSA, принадлежащему получателю «Б» и находящемуся в открытом доступе.
Сообщение и ключ конвертируются в RSA, после чего отправляются пользователю «Б».
Пользователь «Б» может расшифровать полученное письмо при помощи приватного RSA ключа, а доступ к самому тексту сообщения можно получить при использовании DES ключа.

Пример работы

Работа шифрования заключается в трех этапах:

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

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

Исходники программ. Репетитор по программированию. Код для студентов

Вопросами повторного использования готового кода озадачены лучшие «программерские» умы.
Как ни где в мире, использование прошлого опыта целесообразно в области программировании.

Любой студент-второкурсник знает:

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

Продолжу на эту же тему:

Структуры и Классы это вообще клад, так как представляют собой концентрированное выражение знаний
(метаданных и алгоритмов) из определенной области. Сторонние пакеты классов предоставляются в
виде библиотек (например *.dll).;
Найти в нужный момент нужный класс это огромная удача. Иначе придется писать его самому, отлаживать, тестировать.
Но, как говорится, «что Бог ни дает все к лучшему». В этом случае Вы становитесь автором и обладателем
«сокровища». Сохраняйте и берегите его. В нужный момент, Вы обязательно вспомните, что в ваших запасах уже
имеется что-то похожее и пригодное к использованию или доработке.

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

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

Я буду рад, если Вы найдете на этом сайте, что-то полезное, как «детали конструктора». Творите. Перерабатывайте.
Объединяйте и комбинируйте.

В крайнем случае, если цейтнот и времени не хватает катастрофически (а для студентов это очень характерно всегда не хватает
времени и денег), можно поручить сборку мне, т.к. составление пошаговых инструкций для компьютера на одном из языков:
C, C++, C#, Delphi, Visual Basic, Pascal, VBA — является достаточно специфическим видом деятельности. Чтобы им заниматься
— это надо любить.

А с недавнего времени, я добавил услугу Скайп-Консультирование! Это для тех, кто уже пишет код сам,
но вдруг уперся в стену на какой-то мелочи

Ведь Skype предоставляет возможности

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

И это очень эффективно!!!

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

Разумеется, для студентов, что заказали код, час общения по Скайпу остается бесплатным.

А сейчас, ВНИМАНИЕ! Отличительная особенность моих услуг!

Если вы позвоните на указанный телефон, то Вам отвечу я.

Если вы напишите на e-mail, зададите вопрос, пожелаете получить консультацию, то Вам буду отвечать непосредственно я.

Вам не придется общаться с автоответчиками или «блондинками-попугаями», которые отвечают заученными фразами.
Вы будете общаться с первым лицом, которое писало код и несет всю ответственность за проделанную работу.

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

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

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

RSA-шифрование. Описание и реализация алгоритма RSA

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

История создания

Название RSA состоит из начальных букв фамилий Ривест, Шамир и Адлеман, — ученых, которые впервые публично описали подобные алгоритмы шифрования в 1977 году. Клиффорд Кокс, английский математик, работавший на спецслужбы Великобритании, впервые разработал эквивалентную систему в 1973 году, но она не была рассекречена до 1997 г.

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

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

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

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

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

ЭЦП и открытый ключ

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

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

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

В чем суть алгоритма?

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

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

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

Шифрование файлов RSA и слабые места

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

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

Дополнительные алгоритмы шифрования и защиты

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

Безопасность криптосистемы RSA и шифрование информации основаны на двух математических задачах: проблемы разложения на множители больших чисел и собственно проблемы RSA. Полное раскрытие шифротекста и ЭЦП в RSA считается недопустимым на том предположении, что обе эти проблемы невозможно разрешить в совокупности.

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

Автоматизация

Инструмент, называемый Yafu, может быть использован для оптимизации этого процесса. Автоматизация в YAFU представляет собой современную функцию, сочетающую алгоритмы факторизации в интеллектуальной и адаптивной методологии, которая сводит к минимуму время, чтобы найти факторы произвольных входных чисел. Большинство реализаций алгоритма многопоточные, что позволяет Yafu в полной мере использовать мульти- или много многоядерные процессоры (в том числе SNFS, SIQS и ECM). Прежде всего, это управляемый инструмент командной строки. Время, затраченное на поиск фактора шифрования с использованием Yafu на обычном компьютере, может быть уменьшено до 103.1746 секунд. Инструмент производит обработку бинарных файлов емкостью 320 бит или больше. Это очень сложное программное обеспечение, которое требует определенного количества технических навыков для установки и настройки. Таким образом, RSA-шифрование C может оказаться уязвимым.

Попытки взлома в новейшее время

В 2009 году Бенджамин Муди с помощью битового ключа RSA-512 работал над расшифровкой криптотекста в течение 73 дней, используя только общеизвестное программное обеспечение (GGNFS) и среднестатистический настольный компьютер (двухъядерный Athlon64 при 1900 МГц). Как показал данный опыт, потребовалось чуть менее 5 гигабайт диска и около 2,5 гигабайт оперативной памяти для процесса «просеивания».

По состоянию на 2010 год, самый большой факторизованный номер RSA был 768 бит длиной (232 десятичные цифры, или RSA-768). Его раскрытие длилось два года на нескольких сотнях компьютеров одновременно.

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

Перспективы

Поэтому, как правило, предполагается, что RSA является безопасным, если числа достаточно велики. Если же основное число 300 бит или короче, шифротекст и ЭЦП может быть разложен в течение нескольких часов на персональном компьютере с использованием программного обеспечения, имеющегося уже в свободном доступе. Ключи длиной 512 бит, как было доказано, могли быть вскрыты уже в 1999 году с использованием нескольких сотен компьютеров. В наши дни это возможно в течение нескольких недель с использованием общедоступного аппаратного обеспечения. Таким образом, вполне возможно, что в будущембудет легко раскрываться RSA-шифрование на пальцах, и система станет безнадежно устаревшей.

Официально в 2003 году была поставлена под сомнение безопасность 1024-битных ключей. В настоящее время рекомендуется иметь длину не менее 2048 бит.

c — шифрование / дешифрование RSA — qaru
Переполнение стека
Около
Продукты
Для команд
Переполнение стека
Общественные вопросы и ответы
Переполнение стека для команд
Где разработчики и технологи делятся частными знаниями с коллегами
Вакансии
Программирование и связанные с ним технические возможности карьерного роста
Талант
Нанимайте технических специалистов и создавайте свой бренд работодателя
Реклама
Обратитесь к разработчикам и технологам со всего мира
.
c # — Использование открытого ключа RSA для расшифровки строки, зашифрованной с помощью закрытого ключа RSA
Переполнение стека
Около
Продукты
Для команд
Переполнение стека
Общественные вопросы и ответы
Переполнение стека для команд
Где разработчики и технологи делятся частными знаниями с коллегами
Вакансии
Программирование и связанные с ним технические возможности карьерного роста
Талант
Нанимайте технических специалистов и создавайте свой бренд работодателя
Реклама
Обратитесь к разработчикам и технологам со всего мира
О компании
.
No related posts.