Учебный проект Представление данных в компьютере
Причины удаления файлов: некорректное имя файла; не указаны источник и категория (см. правила!)
"Данная страница является результатом труда учащихся 10 класса (физико-математический профиль)" Участник:Максим Дранкин 08:01, 12 октября 2012 (MSK)
Способы шифрования информации
Шифрование - это способ преобразования данных из одного представления в другое — из «открытого» представления в «закрытое». Под «открытым» представлением понимаются данные, содержащие информацию в том виде, в котором она, собственно, существует(например обычный текст), под «закрытым» — видоизмененные данные, которые не содержат изначальной информации сами по себе. Для того чтобы прочитать изначальную информацию, необходимы специальные утройства или программы — дешифраторы. То есть злоумышленник, перехватив зашифрованные данные, не сможет прочитать из них передаваемую информацию. Свойства и особенности шифрования Шифрование применяется для хранения важной информации в ненадёжных источниках или передачи её по незащищённым каналам связи. Шифрование, как процесс, состоит из двух основных частей — зашифрование и расшифрование. Криптография - Наука, изучающая шифрование и его методы В зависимости от алгоритма преобразования данных, методы шифрования подразделяются на: гарантированной криптостойкости. временной криптостойкости. В зависимости от структуры используемых ключей методы шифрования подразделяются на: Симметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, но неизвестна небольшая порция секретной информации — ключа, одинакового для отправителя и получателя сообщения; Асимметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, и, возможно, открытый ключ, но неизвестен закрытый ключ, известный только получателю.
Содержание [показать] Методы шифрования
Содержание: 1 Введение. 2 1.1 Исторические основы криптологии.. 2 1.2 Криптология в современном мире. 3 2 Криптология.. 4 2.1 Основные понятия криптологии.. 4 2.2 Требования к криптосистемам.. 7 2.3 Симметрические криптосистемы.. 8 2.3.1 Метод Цезаря. 9 2.3.2 Системы шифрования Вижинера. 11 2.3.3 Гаммирование. 12 2.4 Криптосистемы с открытым ключом.. 13 2.4.1 Система RSA... 15 2.4.2 Алгоритм Эль-Гамаля. 17 3 Практическое применение криптологии.. 19 3.1 Цифровая подпись. 19 3.1.1 Общие положения. 19 3.1.2 Алгоритм DSA... 20 3.2 Алгоритм DES.. 22 4 Постановка задачи.. 24 5 Реализация задачи.. 24 5.1 Краткая характеристика среды Delphi 7.. 24 5.2 Алгоритм решения задачи.. 24 5.2.1 Модули программы.. 25 5.2.2 Модуль шифровки/дешифровки.. 25 5.2.3 Процедура кодирования символа. 26 5.3 Таблица сообщений.. 26 6 Заключение. 26 7 Список литературы:. 28
1 Введение
1.1 Исторические основы криптологии Понятие "Безопасность" охватывает широкий круг интересов как отдельных лиц, так и целых государств. В наше мобильное время видное место отводится проблеме информированной безопасности, обеспечению защиты конфиденциальной информации от ознакомления с ней конкурирующих групп О важности сохранения информации в тайне знали уже в древние времена, когда с появлением письменности появилась и опасность прочтения ее нежелательными лицами. Существовали три основных способа защиты информации. Один из них предполагал защиту ее чисто силовыми методами: охрана документа - носителя информации -физическими лицами, передача его специальным курьером и т.д. Второй способ получил название "стеганография" (латино-греческое сочетание слов, означающих в совокупности "тайнопись"). Он заключался в сокрытии самого факта наличия информации. В данном случае использовались так называемые симпатические чернила. При соответствующем "проявлении" бумаги текст становится видимым. Один из примеров сокрытия информации приведен в трудах древнегреческого историка Геродота. На голове раба, которая брилась наголо, записывалось нужное сообщение. И когда волосы его достаточно отрастали, раба отправляли к адресату, который снова брил его голову и считывал полученное сообщение. Третий способ защиты информации заключался в преобразовании смыслового текста в некий набор хаотических знаков (или букв алфавита). Получатель данного донесения имел возможность преобразовать его в то же самое осмысленное сообщение, если обладал ключом к его построению. Этот способ защиты информации называется криптографическим. Криптография - слово греческое и в переводе означает "тайнопись". По утверждению ряда специалистов криптография по возрасту - ровесник египетских пирамид. В документах древних цивилизаций - Индии, Египта, Месопотамии - есть сведения о системах и способах составления шифрованных писем. Наиболее полные и достоверные сведения о шифрах относятся к Древней Греции. Основное понятие криптографии - шифр (от арабского "цифра"; арабы первыми стали заменять буквы на цифры с целью защиты исходного текста). Секретный элемент шифра, недоступный посторонним, называется ключом шифра. Как правило, в древние времена использовались так называемые шифры замены и шифры перестановки. Историческим примером шифра замены является шифр Цезаря (1 век до н.э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому языку он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д,Е,...,; затем под ним выписывался тот же алфавит, но со сдвигом на 3 буквы влево. Таким образом, можно утверждать, что основы криптологии были заложены еще в древности и, естественно, после многовекового развития нашли широкое применение в современной жизни. 1.2 Криптология в современном мире На протяжении всей своей многовековой истории, вплоть до совсем недавнего времени, это искусство криптологии немногим, в основном верхушке общества, не выходя за пределы резиденций глав государств, посольств и — конечно же — разведывательных миссий. И лишь несколько десятилетий назад все изменилось коренным образом — информация приобрела самостоятельную коммерческую ценность и стала широко распространенным, почти обычным товаром. Ее производят, хранят, транспортируют, продают и покупают, а значит — воруют и подделывают — и, следовательно, ее необходимо защищать. Современное общество все в большей степени становится информационно—обусловленным, успех любого вида деятельности все сильней зависит от обладания определенными сведениями и от отсутствия их у конкурентов. И чем сильней проявляется указанный эффект, тем больше потенциальные убытки от злоупотреблений в информационной сфере, и тем больше потребность в защите информации. Среди всего спектра методов защиты данных от нежелательного доступа особое место занимают криптографические методы. В отличие от других методов, они опираются лишь на свойства самой информации и не используют свойства ее материальных носителей, особенности узлов ее обработки, передачи и хранения. Образно говоря, криптографические методы строят барьер между защищаемой информацией и реальным или потенциальным злоумышленником из самой информации. Конечно, под криптографической защитой в первую очередь подразумевается шифрование данных. Раньше эта операция выполнялось человеком вручную или с использованием различных приспособлений. Поэтому развитие криптологии сдерживалось проблемой реализации шифра. Почему же проблема использования криптографических методов в информационных системах (ИС) стала в настоящий момент особо актуальна? С одной стороны, расширилось использование компьютерных сетей, в частности глобальной сети Интеpнет, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ней посторонних лиц. С другой стороны, появление новых мощных компьютеров, технологий сетевых и нейронных вычислений сделало возможным дискредитацию криптографических систем еще недавно считавшихся практически не раскрываемыми.
2 Криптология
2.1 Основные понятия криптологии Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих направлений прямо противоположны. Криптография занимается поиском и исследованием математических методов преобразования информации. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей. Современная криптография включает в себя четыре крупных раздела: 1. Симметричные криптосистемы. 2. Криптосистемы с открытым ключом. 3. Системы электронной подписи. 4. Управление ключами. Основные направления использования криптографических методов - передача конфиденциальной информации по каналам связи (например, электронная почта), установление подлинности передаваемых сообщений, хранение информации (документов, баз данных) на носителях в зашифрованном виде. Криптографические методы защиты информации в автоматизированных системах могут применяться как для защиты информации, обрабатываемой в ЭВМ или хранящейся в различного типа ЗУ, так и для закрытия информации, передаваемой между различными элементами системы по линиям связи. Криптографическое преобразование как метод предупреждения несанкционированного доступа к информации имеет многовековую историю. В настоящее время разработано большое количество различных методов шифрования, созданы теоретические и практические основы их применения. Подавляющие число этих методов может быть успешно использовано и для закрытия информации. Итак, криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа. В качестве информации, подлежащей шифрованию и дешифрованию, рассматриваются тексты, построенные на некотором алфавите. Под этими терминами понимается следующее. Алфавит - конечное множество используемых для кодирования информации знаков. Текст - упорядоченный набор из элементов алфавита. В качестве примеров алфавитов, используемых в современных ИС можно привести следующие: · алфавит Z33 - 32 буквы русского алфавита и пробел; · алфавит Z256 - символы, входящие в стандартные коды ASCII и КОИ-8; · бинарный алфавит - Z2 = {0,1}; · восьмеричный алфавит или шестнадцатеричный алфавит; Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом. Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный. Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов. Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита. Криптосистемы разделяются на симметричные и с открытым ключом. В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ. В системах с открытым ключом используются два ключа - открытый и закрытый, которые математически связаны друг с другом. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения. Термины распределение ключей и управление ключами относятся к процессам системы обработки информации, содержанием которых является составление и распределение ключей между пользователями. Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения. Криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа(т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых: -количество всех возможных ключей; -среднее время, необходимое для криптоанализа. Преобразование Tk определяется соответствующим алгоритмом и значением параметра k. Эффективность шифрования с целью защиты информации зависит от сохранения тайны ключа и криптостойкости шифра. Процесс криптографического закрытия данных можетм осуществляться как программно, так и аппаратно. Аппаратная реализация отличается существенно большей стоимостью, однако ей присущи и преимущества: высокая производительность, простота, защищенность и т.д. Программная реализация более практична, допускает известную гибкость в использовании. 2.2 Требования к криптосистемам Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования: -зашифрованное сообщение должно поддаваться чтению только при наличии ключа; -число операций, необходимых для определения использованного ключа шифрования по фрагменту шифрованного сообщения и соответствующего ему открытого текста, должно быть не меньше общего числа возможных ключей; -число операций, необходимых для расшифровывания информации путем перебора всевозможных ключей должно иметь строгую нижнюю оценку и выходить за пределы возможностей современных компьютеров (с учетом возможности использования сетевых вычислений); -знание алгоритма шифрования не должно влиять на надежность защиты; -незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа; -структурные элементы алгоритма шифрования должны быть неизменными; -дополнительные биты, вводимые в сообщение в процессе шифрования, должен быть полностью и надежно скрыты в шифрованном тексте; -длина шифрованного текста должна быть равной длине исходного текста; -не должно быть простых и легко устанавливаемых зависимостью между ключами, последовательно используемыми в процессе шифрования; -любой ключ из множества возможных должен обеспечивать надежную защиту информации; -алгоритм должен допускать как программную, так и аппаратную реализацию, при этом изменение длины ключа не должно вести к качественному ухудшению алгоритма шифрования.
2.3 Симметрические криптосистемы Долгое время традиционной криптографической схемой была схема с симметричным ключом. В этой схеме имеется один ключ, который участвует в шифровании и дешифровании информации. Шифрующая процедура при помощи ключа производит ряд действий над исходными данными, дешифрующая процедура при помощи того же ключа производит обратные действия над кодом. Дешифрование кода без ключа предполагается практически неосуществимым. Если зашифрованная таким образом информация передается по обычному, т.е. незащищенному, каналу связи, один и тот же ключ должен иметься у отправителя и получателя, вследствие чего возникает необходимость в дополнительном защищенном канале для передачи ключа, повышается уязвимость системы и увеличиваются организационные трудности. Открытый текст обычно имеет произвольную длину если его размер велик и он не может быть обработан вычислительным устройством шифратора целиком, то он разбивается на блоки фиксированной длины, и каждый блок шифруется в отдельности, не зависимо от его положения во входной последовательности. Такие криптосистемы называются системами блочного шифрования. На практике обычно используют два общих принципа шифрования: рассеивание и перемешивание. Рассеивание заключается в распространении влияния одного символа открытого текста на много символов шифртекста: это позволяет скрыть статистические свойства открытого текста. Развитием этого принципа является распространение влияния одного символа ключа на много символов шифрограммы, что позволяет исключить восстановление ключа по частям. Перемешивание состоит в использовании таких шифрующих преобразований, которые исключают восстановление взаимосвязи статистических свойств открытого и шифрованного текста. Распространенный способ достижения хорошего рассеивания состоит в использовании составного шифра, который может быть реализован в виде некоторой последовательности простых шифров, каждый из которых вносит небольшой вклад в значительное суммарное рассеивание и перемешивание. В качестве простых шифров чаще всего используют простые подстановки и перестановки. Все многообразие существующих криптографических методов можно свести к следующим классам преобразований: Многоалфавитная подстановка - наиболее простой вид преобразований, заключающийся в замене символов исходного текста на другие (того же алфавита) по более или менее сложному правилу. Для обеспечения высокой криптостойкости требуется использование больших ключей. Перестановки - несложный метод криптографического преобразования. Используется как правило в сочетании с другими методами. Гаммирование - этот метод заключается в наложении на исходный текст некоторой псевдослучайной последовательности, генерируемой на основе ключа. Блочные шифры представляют собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем “чистые” преобразования того или иного класса в силу их более высокой криптостойкости, а также потому, что этот метод позволяет шифровать тексты практически любой длины, разбивая их на блоки. Российский и американский стандарты шифрования основаны именно на этом классе шифров. 2.3.1 Метод Цезаря Метод Цезаря является самым простым вариантом шифрования. Он назван по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита, сдвигая его на 3 символа вперед. Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст — шифрованный текст”. Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки преобразуется в еюыолхиврсеюивцнгкгрлб. Аàг Йàм Тàх Ыàю Бàд Кàн Уàц Ьàя Вàе Лàо Фàч Эà_ Гàж Мàп Хàш Юàа Дàз Нàр Цàщ Яàб Еàи Оàс Чàъ _àв Жàй Пàт Шàы Зàк Рàу Щàь Иàл Сàф Ъàэ Таблица 1.1: Применение подстановки Цезвря. При своей несложности система легко уязвима. Если злоумышленник имеет 1) шифрованный и соответствующий исходный текст или 2) шифрованный текст выбранного злоумышленником исходного текста, то определение ключа и дешифрование исходного текста тривиальны. Эту систему не представляет труда взломать с помощью современной вычислительной техники, используя простой перебор. Поэтому криптостойкость этого метода не велика. Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации. 2.3.2 Системы шифрования Вижинера Метод Вижинера является следствием подстановки Цезаря. В системе Вижинера задается некая конечная последовательность ключа k = (k0 ,k1 ,...,kn), которая называется ключом пользователя, она продолжается до бесконечной последовательности, повторяя цепочку. Таким образом, получается рабочий ключ Например, при ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической последовательностью: 15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ... Таким образом: При длине пользовательского ключа R 1) исходный текст x делится на R фрагментов xi = (xi , xi+r , ..., xi+r(n-1)), 0 £ i < r; 2) i-й фрагмент исходного текста xi шифруется при помощи подстановки Цезаря в зависимости от пользовательского ключа : (xi , xi+r , ..., xi+r(n-1)) ® (yi , yi+r , ..., yi+r(n-1)), Очень распространена плохая с точки зрения секретности практика использовать слово или фразу в качестве ключа для того, чтобы k=(k0 ,k1 ,...,kк-1) было легко запомнить. В информационных системах для обеспечения безопасности информации это недопустимо. Для получения ключей должны использоваться программные или аппаратные средства случайной генерации ключей. Пример. Преобразование текста с помощью подстановки Вижинера (r=4) Исходный текст (ИТ1): НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ Ключ: КЛЮЧ Разобьем исходный текст на блоки по 4 символа: НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ и наложим на них ключ (используя таблицу Вижинера): H+К=Ч, Е+Л=Р и т.д. Получаем зашифрованный (ЗТ1) текст: ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН Криптостойкость метода резко убывает с уменьшением длины ключа. Тем не менее такая система как шифр Вижинера допускает несложную аппаратную или программную реализацию и при достаточно большой длине ключа может быть использован в современных ИС. 2.3.3 Гаммирование Гаммирование является также широко применяемым криптографическим преобразованием. На самом деле граница между гаммированием и использованием бесконечных ключей и шифров Вижинера, о которых речь шла выше, весьма условная. Принцип шифрования гаммированием заключается в генерации гаммы шифра с помощью датчика псевдослучайных чисел и наложении полученной гаммы на открытые данные обратимым образом. Процесс дешифрования данных сводится к повторной генерации гаммы шифра при известном ключе и наложении такой гаммы на зашифрованные данные. Полученный зашифрованный текст является достаточно трудным для раскрытия в том случае, если гамма шифра не содержит повторяющихся битовых последовательностей. По сути дела гамма шифра должна изменяться случайным образом для каждого шифруемого слова. Фактически же, если период гаммы превышает длину всего зашифрованного текста и неизвестна никакая часть исходного текста, то шифр можно раскрыть только прямым перебором (пробой на ключ). Криптостойкость в этом случае определяется размером ключа. Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок ПСП и по нему восстанавливается вся последовательность. Злоумышленники может сделать это на основе догадок о содержании исходного текста. Так, если большинство посылаемых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается. Это следует учитывать при создании реальных систем информационной безопасности. 2.4 Криптосистемы с открытым ключом В 1976 г. У.Диффи и М.Хеллманом был предложен новый тип криптографической системы - система с открытым ключом [public keycryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом - упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа. С появлением систем с открытым ключом понятие о защите информации, а вместе с ним функции криптографии значительно расширились. Если раньше основной задачей криптографических систем считалось надежное шифрование информации, в настоящее время область применения криптографии включает также цифровую подпись(аутентификацию), лицензирование, нотаризацию (свидетельствование), распределенное управление, схемы голосования, электронные деньги и многое другое . Наиболее распространенные функции криптографических систем с открытым ключом - шифрование и цифровая подпись, причем роль цифровой подписи в последнее время возросла по сравнению с традиционным шифрованием: некоторые из систем с открытым ключом поддерживают цифровую подпись, но не поддерживают шифрование. Цифровая подпись используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Она аналогична обычной рукописной подписи и обладает ее основными свойствами: удостоверяет, что подписанный текст исходит именно от лица, поставившего подпись, и не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом. Цифровая подпись представляет собой небольшое количество дополнительной информации, передаваемой вместе с подписываемым текстом. В отличие от шифрования, при формировании подписи используется секретный ключ, а при проверке - открытый. Из-за особенностей алгоритмов, лежащих в основе систем с открытым ключом, их быстродействие при обработке единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке той же длины. Для повышения эффективности систем с открытым ключом часто применяются смешанные методы, реализующие криптографические алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного текста. а затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа -полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция(дайджест) [one-way hash function, digest], представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или подбора другого текста, имеющего ту же хэш-функцию, практически неразрешима. При непосредственном формировании подписи, вместо шифрования секретным ключом каждого блока текста секретный ключ применяется только к хэш-функции; по каналу передается сам текст и сформированная подпись хэш-функции. Для проверки подписи снова вычисляется хэш-функция от полученного по каналу текста, после чего при помощи открытого ключа проверяется, что подпись соответствует именно данному значению хэш-функции. Алгоритмы вычисления однонаправленных хэш-функций, как правило, логически тесно связаны с алгоритмами шифрования с симметричным ключом. Описанные гибридные методы шифрования и цифровой подписи сочетают в себе эффективность алгоритмов с симметричным ключом и свойство независимости от дополнительных секретных каналов для передачи ключей, присущее алгоритмам с открытым ключом. Криптографическая стойкость конкретного гибридного метода определяется стойкостью слабейшего звена в цепи, состоящей из алгоритмов с симметричным и с открытым ключом, выбранных для его реализации. 2.4.1 Система RSA Самым распространенным алгоритмом ассиметричного шифрования является алгоритм RSA. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел. Современное состояние алгоритмов факторизации (разложения на множители) позволяет решать эту задачу для чисел длиной до 430 бит; исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных на срок до 10 лет, а в 1024 бита — безусловно надежным. Несмотря на то, что отсутствует математически доказанное сведение задачи раскрытия RSA к задаче разложения на множители, система выдержала испытание практикой и является признанным стандартом de-facto в промышленной криптографии, а также официальным стандартом ряда международных организаций. С другой стороны, свободное распространение программного обеспечения, основанного на RSA, ограничено тем, что алгоритм RSA защищен в США рядом патентов. RSA можно применять как для шифрования/расшифровывания, так и для генерации/проверки электронно-цифровой подписи. 2.4.1.1 Генерация ключа Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций : Выбираются два простых (!) числа p и q Вычисляется их произведение n(=p*q) Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1). Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y — метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах. Два числа (e,n) — публикуются как открытый ключ. Число d хранится в строжайшем секрете — это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n). 2.4.1.2 Шифрование/расшифровывание Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа. Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi. А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y) : (x(-y)(p-1)(q-1))mod n = 1(-y) = 1. Теперь умножим обе ее части на x : (x(-y)(p-1)(q-1)+1)mod n = 1*x = x. А теперь вспомним как создавались открытый и закрытый ключи. с помощью алгоритма Евклида подбиралось такое d, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m : ((ci)d)mod n = ((mi)e*d)mod n = mi. На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла. 2.4.2 Алгоритм Эль-Гамаля 2.4.2.1 Общие сведения В 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P. Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P. 2.4.2.2 Шифрование сообщений Протокол передачи сообщения M выглядит следующим образом. абоненты знают числа A и P; абоненты генерируют независимо друг от друга случайные числа: Ka, Kb удовлетворяющих условию: 1 < K < P получатель вычисляет и передаёт отправителю число B, определяемое последовательностью: В = A Kb mоd(P) отправитель шифрует сообщение M и отправляет полученную последовательность получателю C = M * B Ka mоd(P) получатель расшифровывает полученное сообщение D = ( A Ka ) -Kb mоd(P) M = C * D mоd(P) В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений. 2.4.2.3 Подтверждение подлинности отправителя Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M: абоненты знают числа A и P; отправитель генерирует случайное число и хранит его в секрете: Ka удовлетворяющее условию: 1 < Ka < P вычисляет и передаёт получателю число B, определяемое последователньостью: В = A Ka mоd(P) Для сообщения M (1 < M < P): выбирает случайное число L (1 < L < P), удовлетворяющее условию ( L , P - 1 ) = 1 вычисляет число R = A L mоd(P) решает относительно S M = Ka * R + L * S mоd(P) передаёт подписанное сообщение [ M, R, S ] получатель проверяет правильность подписи A M = ( B R ) * ( R S ) mоd(P) В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Процедура проверки подписи служит также и для проверки правильности расшифровывания, если сообщения шифруются.
3 Практическое применение криптологии
3.1 Цифровая подпись 3.1.1 Общие положения При ведении деловой переписки, при заключении контрактов подпись ответственного лица является непременным атрибутом документа, преследующим несколько целей: - Гарантирование истинности письма путем сличения подписи с имеющимся образцом; - Гарантирование авторства документа ( с юридической точки зрения) Выполнение данных требований основывается на следующих свойствах подписи: - подпись аутентична, то есть с ее помощью получателю документа можно доказать, что она принадлежит подписывающему; - подпись неподделываема; то есть служит доказательством, что только тот человек, чей автограф стоит на документе, мог подписать данный документ, и никто иной. - Подпись непереносима, то есть является частью документа и поэтому перенести ее на другой документ невозможно. - Документ с подписью является неизменяемым. - Подпись неоспорима. - Любое лицо, владеющее образцом подписи может удостоверится, что документ подписан владельцем подписи. - Развитие современных средств безбумажного документооборота, средств электронных платежей немыслимо без развития средств доказательства подлинности и целостности документа. Таким средством является электронно-цифровая подпись (ЭЦП), которая сохранила основные свойства обычной подписи. Существует несколько методов построения ЭЦП, а именно: - шифрование электронного документа (ЭД) на основе симметричных алгоритмов. Данная схема предусматривает наличие в системе третьего лица — арбитра, пользующегося доверием обеих сторон. Авторизацией документа в данной схеме является сам факт шифрования ЭД секретным ключом и передача его арбитру. - Использование ассиметричных алгоритмов шифрования. Фактом подписания документа является шифрование его на секретном ключе отправителя. - Развитием предыдущей идеи стала наиболее распространенная схема ЭЦП — шифрование окончательного результата обработки ЭД хеш-функцией при помощи ассиметричного алгоритма. Кроме перечисленных, существуют и другие методы построения схем ЭЦП - групповая подпись, неоспариваемая подпись, доверенная подпись и др. Появление этих разновидностей обусловлено разнообразием задач, решаемых с помощью электронных технологий передачи и обработки электронных документов. 3.1.2 Алгоритм DSA В 1991 г. в США был опубликован проект федерального стандарта цифровой подписи - DSS (Digital Signature Standard, [DSS91], описывающий систему цифровой подписи DSA (Digital Signature Algorithm). Одним из основных критериев при создании проекта была его патентная чистота. Предлагаемый алгоритм DSA, имеет, как и RSA, теоретико-числовой характер, и основан на криптографической системе Эль-Гамаля в варианте Шнорра. Его надежность основана на практической неразрешимости определенного частного случая задачи вычисления дискретного логарифма. Современные методы решения этой задачи имеют приблизительно ту же эффективность, что и методы решения задачи факторизации; в связи с этим предлагается использовать ключи длиной от 512 до 1024 бит с теми же характеристиками надежности, что и в системе RSA. Длина подписи в системе DSA меньше, чем в RSA, и составляет 320 бит. С момента опубликования проект получил много критических отзывов, многие из которых были учтены при его доработке. Одним из главных аргументов против DSA является то, что, в отличие от общей задачи вычисления дискретного логарифма, ее частный случай, использованный в данной схеме, мало изучен и, возможно, имеет существенно меньшую сложность вскрытия. Кроме того, стандарт не специфицирует способ получения псевдослучайных чисел, используемых при формировании цифровой подписи, и не указывает на то, что этот элемент алгоритма является одним из самых критичных по криптографической стойкости. Функции DSA ограничены только цифровой подписью, система принципиально не предназначена для шифрования данных. По быстродействию система DSA сравнима с RSA при формировании подписи, но существенно (в 10-40 раз) уступает ей при проверке подписи. 3.1.2.1 Генерация ЭЦП При генерации ЭЦП используются параметры трех групп: общие параметры секретный ключ открытый ключ Общие параметры необходимы для функционирования системы в целом. Секретный ключ используется для формирования ЭЦП, а открытый — для проверки ЭЦП. Общими параметрами системы являются простые целые числа p,q,g, удовлетворяющие следующим условиям: p: 2^511<p<2^512 q: простой делитель числа (p-1), который удовлетворяет условию 2^159<q<2^160 g: так называемый генератор, удовлетворяющий равенству g=h^((p-1)/q)mod p >1. Параметры p,q,g публикуются для всех участников обмена ЭД с ЭЦП. Секретный ключ x случайно выбирается из диапазона [1,q] и держится в секрете. Открытый ключ вычисляется: y=g^x mod p. Также при описании данной схемы будут использоваться следующие обозначения и дополнительные параметры: m — входное сообщение пользователя для схемы с ЭЦП; k - случайное число, удовлетворяющее условию 0<k<q, хранящееся в секрете и меняющееся от одной подписи к другой; H — хэш-функция, h — хэш-код сообщения. Процесс генерации ЭЦП состоит из нескольких этапов: 1.Вычисляется хэш-код сообщения m h=H(m) 2.Из диапазона [1,q] случайным образом выбирается значение k и вычисляется r= (g^k mod p) mod q 3. Вычисляется S= (k^-1(h+xr)) mod q, где k^-1 удовлетворяет условию (k^-1*k) mod q =1 Значения r,s являются ЭЦП сообщения m и передаются вместе с ним по каналам связи. 3.1.2.2 Проверка ЭЦП Пусть принято сообщение m1 и его подпись s1,r1. Проверка ЭЦП происходит следующим образом: - проверяется выполнение условий 0<r1<q, 0<s1<q, и если хотя бы одно из них нарушено, подпись отвергается. - Вычисляются значения: w= s1^-1 mod q u1 = (H(m1)w) mod q u2 = ((r1/w) mod q v = (( g^u1y^u2) mod p ) mod q - проверяется равенство v = r1 Если последнее равенство выполняется, то подпись принимается. В данном стандарте специфицируется также процедура генерации основных параметров системы и проводится доказательство того, что если v=r1, то m1=m, r1=r, s1=s. 3.2 Алгоритм DES Принятие стандарта шифрования DES явилось мощным толчком к широкому применению шифрования в коммерческих системах. Введение этого стандарта - отличный пример унификации и стандартизации средств защиты. Примером системного подхода к созданию единой крупномасштабной системы защиты информации является директива Министерства финансов США 1984 года, согласно которой все общественные и частные организации, ведущие дела с правительством США, обязаны внедрить процедуру шифрования DES; крупнейшие банки Citibank,Chase Manhattan Bank, Manufaktures Hannover Trust, Bank of America, Security Pacific Bank также внедрили эту систему. Министерство энергетики США располагает более чем 30 действующими сетями, в которых используется алгоритм DES, Министерство юстиции устанавливает 20000 радиоустройств, располагающих средствами защиты на базе DES. Стандартизация в последнее время приобретает международный характер, подтверждение тому - международный стандарт 1987 года ISO 8372, разработанный на основе криптоалгоритма DES. В качестве стандартной аппаратуры шифрования можно назвать устройство Cidex-НХ, базирующееся на алгоритме DES; скорость шифрования - от 56 Кбит/с до 7 Мбит/с. Серийно выпускается автономный шифровальный блок DES 2000, в нем также используется процедура шифрования DES; скорость шифрования - от 38,4 Кбит/с до 110 Кбит/с. В различных секторах коммерческой деятельности используется процессор шифрования/дешифрования данных FACOM 2151А на основе алгоритма DES; скорость - от 2,4 Кбит/с до 19,2 Кбит/с. С распространением персональных компьютеров наиболее эффективными для них стали программные средства защиты. Так, разработан пакет программ для шифрования/дешифрования информации СТА (Computer Intelligence Access), реализующий алгоритм DES. Этот же алгоритм использован в пакете SecretDisk (C F Systems) для исключения несанкционированного доступа к дискам. Таким образом, алгоритм DES представляет собой основной механизм, применявшийся частными и государственными учреждениями США для защиты информации. В то же время Агентство национальной безопасности, выступающее как эксперт по криптографическим алгоритмам, разрабатывает новые алгоритмы шифрования данных для массового использования. В 1987 году Национальное бюро стандартов после обсуждения подтвердило действие DES; его пересмотр намечалось провести не позднее января 1992 года, и на сегодняшний день действие DES ограничивается исключительно коммерческими системами.
4 Постановка задачи
Разработать программу шифрующую и дешифрующую введенный пользователем текст. Обеспечить ввод и вывод информации с помощью файлов. Обеспечить достаточную криптоустойчивость шифра.
5 Реализация задачи
5.1 Краткая характеристика среды Delphi 7 Среда программирования Delphi 7 позволяет реализовать поставленную задачу со всеми необходимыми требованиями. В среде используется язык Object Pascal. Delphi 7 является объектно-ориентированной средой, что упрощает создание единообразного интерфейса и ввод-вывод информации из файла. 5.2 Алгоритм решения задачи Программа представляет собой шифровщик и дешифровщик одновременно. Используется метод симметрического кодирования, то есть кодирование и декодирование осуществляется с помощью одного ключа. Для обеспечения криптоустойчивости необходим длинный ключ. Пользователь вводит 30-символьный код. Блоками по 10 цифр. Из них генерируется код следующим образом: Берутся первые цифры из 1-го, 2-го,3-го блоков, и в зависимости от 3-го блока над ними производятся операции сложения или умножения. Затем берется следующая цифра 3-го блока, после полного завершения цикла по 3-му блоку берется следующая цифра из второго блока и т.д. Гаммирование завершается после прохождения по циклу последней цифры 1-го блока. Результатом является код состоящий из 1000 независимых, неповторяющихся и незакономерных цифр. Шифр возможно вскрыть только полным перебором, что обеспечивает достаточную криптоустойчивость. 5.2.1 Модули программы Программа имеет несколько стандартных основных модулей: вызов справки, сохранение в файл, открытие файла, генерация произвольного ключа, проверка пароля, которые не будут упоминаться в дальнейшем. Опишем лишь модули отвечающие непосредственно за шифрование. 5.2.2 Модуль шифровки/дешифровки Взятие кодовых цифр из блоков Чтение отдельного символа исх. текста Кодирование символа Конец исх. текста Сохр. результата s1:=memo1.Text; k:=length(s); k1:=length(s1); k3:=length(s3); k5:=length(s5); m:=1; m3:=1; m5:=1; for i:=1 to k1 do begin q:=false; i5:=strtoint(s[m]); i2:=strtoint(s3[m3]); i3:=strtoint(s5[m5]); i1:=kod(i5,i2,i3); if i1=0 then i1:=10; case s1[i] of 'a'..'z':begin c1:=perevod(s1[i],i1,96,122); q:=true; end; 'A'..'Z':begin c1:=perevod(s1[i],i1,64,90); q:=true; end; 'А'..'Я':begin c1:=perevod(s1[i],i1,191,223); q:=true; end; 'а'..'я':begin c1:=perevod(s1[i],i1,223,255); q:=true; end; end; if q=true then begin {if ord(s1[i])+i1>255 then } s2:=s2+c1; { else s2:=s2+chr(ord(s1[i])+i1);} end else s2:=s2+s1[i]; q1:=false; if m5=k5 then begin m5:=1; q1:=true; end else inc(m5); q2:=false; if (q1=true) then begin inc(m3); end; if m3>=k3 then begin m3:=1; q2:=true end; if (q2=true) then m:=m+1; if m>=k then m:=1; end; {delete(s2,k1-1,2)} memo2.Text:=s2; 5.2.3 Процедура кодирования символа begin if abs(i1)>y-x+1 then repeat i1:=i1 mod (y-x+1); until i1<(y-x+1); if ord(c)+i1>y then perevod:=chr(x+(ord(c)‹y)) else perevod:=chr(ord(c)+i1) end; 5.3 Таблица сообщений В ходе работы пользователь может получить сообщение: «Пароль не подтвержден»-следует убедиться в правильности пароля в дублирующих и основных полях.
6 Заключение
Итак, итогом работы является симметрическая криптосистема, работающая на методе гаммирования. Обоснованный выбор той или иной системы защиты должен опираться на какие-то критерии эффективности. К сожалению, до сих пор не разработаны подходящие методики оценки эффективности криптографических систем. Наиболее простой критерий такой эффективности - вероятность раскрытия ключа или мощность множества ключей (М). По сути это то же самое, что и кpиптостойкость. Для ее численной оценки можно использовать также и сложность раскрытия шифра путем перебора всех ключей. Однако, этот критерий не учитывает других важных требований к криптосистемам: · невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры, · совершенство используемых протоколов защиты, · минимальный объем используемой ключевой информации, · минимальная сложность реализации (в количестве машинных операций), ее стоимость, · высокая оперативность. В любом случае выбранный комплекс кpиптогpафических методов должен сочетать как удобство, гибкость и оперативность использования, так и надежную защиту от злоумышленников циркулирующей в ИС информации. Поэтому на настоящий момент наиболее оптимальны смешанные криптосиситемы, в которых текст кодируется симметрически, а ключ кодируется ассиметрически и помещается вместе с кодированным текстом.
7 Список литературы:
1. Петров А.А Компьютерная безопасность. Криптографические методы защиты. ДМК Москва, 2000 г. 2. "Методы и средства защиты информации" (курс лекций) Авторские права: Беляев А.В. (http://www.citforum.ru/internet/infsecure/index.shtml) 3. Криптография (http://www.citforum.ru/internet/securities/crypto.shtml) 4. Бобровский С. Delphi 7. Учебный курс. Из-во Питер, 2004г а также другие источники ==Источники == http://ru.wikipedia.org http://www.studfiles.ru
Кодирование текстовой информации
Информация в компьютере представлена в двоичном коде, алфавит которого состоит из двух цифр (0,1).Каждая цифра машинного двоичного кода несет количество информации, равное одному биту. В одном бите памяти хранится один бит информации . Традиционно для того чтобы закодировать один символ используют количество информации равное 1 байту, т. е. I = 1 байт = 8 бит. При помощи формулы, которая связывает между собой количество возможных событий К и количество информации I, можно вычислить сколько различных символов можно закодировать (считая, что символы - это возможные события):
К = 2^i = 28 = 256, т. е. для представления текстовой информации можно использовать алфавит мощностью 256 символов.
Таблица, в которой всем символам компьютерного алфавитапоставлены в соответствие порядковые номера, называют таблицей кодировки. Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавита, цифры, знаки, графические символы и пр. Все символы компьютерного алфавита пронумерованы от 0 до 255. Кодирование заключается в том, что каждому номеру соответствует восьмиразрядный двоичный код от 00000000 до 11111111. Этот код просто порядковый номер символа в двоичной системе счисления.
В процессе вывода на экран компьютера производится обратный процесс – декодирование, то есть преобразование кода символа в его изображение
При вводе в компьютер текстовой информации происходит ее двоичное кодирование, изображение символа преобразуется в его двоичный код. Пользователь нажимает на клавиатуре клавишу с символом, и в компьютер поступает определенная последовательность из восьми электрических импульсов (двоичный код символа).
Для разных типов ЭВМ используются различные таблицы кодировки. С распространением персональных компьютеров типа IBM PC международным стандартом стала таблица кодировки под названием ASCII (American Standart Code for Information Interchange) – американский стандартный код для информационного обмена.
Таблицы кодирования:
Файл:Asc1.jpg
Пример : Запишем двоичную кодировку слова «file». Очевидно, в памяти компьютера оно займет 4 байта: f -------- 01100110
i --------- 01101001
l --------- 01101100
e ------- 01100101
--Агишева Луиза 19:08, 31 октября 2012 (MSK)
Алфавитный и содержательный подходы к измерению информации.
Единицы измерения информации.
История чисел и систем счисления. Непозиционные системы счисления.
Не позиционные системы счисления появились исторически первыми. В этих системах значение каждого цифрового символа постоянно и не зависит от его положения. Простейшим случаем не позиционной системы является единичная, для которой для обозначения чисел используется единственный символ, как правило это черта, иногда точка, которых всегда ставится количество, соответствующее обозначаемому числу:
1 — | 2 — || 3 — |||, и т. д.
Таким образом, этот единственный символ имеет значение единицы, из которой последовательным сложением получается необходимое число:
||||| = 1+1+1+1+1 = 5.
Модификацией единичной системы является система с основанием, в которой есть символы не только для обозначения единицы, но и для степеней основания. Например, если за основание взято число 5, то будут дополнительные символы для обозначения 5, 25, 125 и так далее.
Египетская система счисления
Египетская система счисления — непозиционная система счисления, которая употреблялась в Древнем Египте вплоть до начала X века н.э. В этой системе цифрами являлись иероглифические символы; они обозначали числа 1, 10, 100 и т. д. до миллиона.
| Число | Значение | Описание |
|---|---|---|
|
1 | черта |
|
10 | пятка |
|
100 | петля веревки |
|
1000 | цветок лотоса |
|
10000 | палец |
|
100000 | жаба |
|
1000000 | человек с поднятыми вверх руками |
Все остальные числа составлялись из этих ключевых при помощи операции сложения. Система счисления Древнего Египта является десятичной, но не позиционной. Например, чтобы изобразить 3252 рисовали три цветка лотоса (три тысячи), две петли веревки (две сотни), пять пяток (пять десятков) и две черты (две единицы): Величина числа не зависела от того, в каком порядке располагались составляющие его знаки: их можно было записывать сверху вниз, справа налево или вперемежку.
Надпись на стеле (пример чисел в правой части рисунка).
Римская система счисления
Римская система счисления - непозиционная система счисления, в которой для записи чисел используются буквы латинского алфавита: 1 - I, 5 - V, 10 - X, 50 - L, 100 - C, 500 - D и 1000 - M.
Римские цифры — цифры, использовавшиеся древними римлянами в своей непозиционной системе счисления. Натуральные числа записываются при помощи повторения этих цифр. При этом, если большая цифра стоит перед меньшей, то они складываются (принцип сложения), если же меньшая — перед большей, то меньшая вычитается из большей (принцип вычитания). Последнее правило применяется только во избежание четырёхкратного повторения одной и той же цифры. Считается, что римские цифры были изобретены не самими римлянами, а их историческими предшественниками - этрусками. Римляне заимствовали эти цифры за пять веков до н. э., усовершенствовали их и правила их использования и передали им свое имя. От римлян римские цифры перешли к другим народам Европы и были в употреблении до XIII - XV вв. На смену им пришли арабские цифры. Римские цифры также имеют свой алфавит с соответствующими характеристиками.
Состав алфавита
В системе римских цифр всего лишь семь знаков: I, V, Х, L, С, О, М. Иногда как отдельные цифры указывают еще II, III, IV, VI и т. п., но это уже сочетания цифр. Значения цифр I – один (1), V - пять (5), Х - десять (10), L – пятьдесят (50), С - сто (100), D - пятьсот (500), М - тысяча (1000). Происхождение (этимология) этих значений толкуется по-разному. Наиболее приемлемы следующие разъяснения: первые три знака - наследие счета по пальцам: I - один палец, V - два разведенных пальца как представители всех пяти пальцев кисти (или кисть руки с отведенным большим пальцем), Х - две «пятерки». Менее других ясны знаки для 50 (L) и500 (D). Названиями римских цифр являются соответствующие имена числительные: Х - десять, С - сто и т. п.
Применении римских цифр
Хотя римская нумерация была не слишком удобной, она распространилась по всей ойкумене - так называли древние греки известный им обитаемый мир. Когда-то римляне завоевали многие страны и присоединили их к своей империи. Со всех этих стран они взимали громадные налоги и, конечно, пользовались при этом своими обозначениями чисел. Так что пришлось жителям этих стран учить римскую нумерацию, посылая все проклятия на головы поработителей. И даже после того, как рухнула Римская империя, в деловых бумагах Западной Европы применялась эта неудобная нумерация. В русском языке римские цифры используются в следующих случаях: - номер века или тысячелетия: XIX век, II тысячелетие до н. э. - порядковый номер монарха: Карл V, Екатерина II. - номер тома в многотомной книге (иногда — номера частей книги, разделов или глав). - маркировка циферблатов часов «под старину». - важные события или пункты списка, например: V постулат Евклида, II мировая война, XXII съезд КПСС и т. п. В других языках сфера применения римских цифр может иметь особенности, например, в западных странах римскими цифрами иногда записывается номер года.
Правило записи больших чисел римскими числами
Для правильной записи больших чисел римскими цифрами необходимо сначала записать число тысяч, затем сотен, затем десятков и, наконец, единиц. Пример: число 1988. Одна тысяча M, девять сотен CM, восемьдесят LXXX, восемь VIII. Запишем их вместе: MCMLXXXVIII.
Преобразование арабских цифр в римские
1. Если в числе отсутствуют цифры 4 и / или 9 Ситуация очень проста. Число разбивается на римской тысяч рублей (500,) сотни (пятидесятые годы), в десятки и единицы (т.е. с максимальной до минимальной):
1763 = 1000 + 700 + 60 + 3 = 1000 + 500 + 100 + 100 + 50 + 10 + 1 + 1 + 1 = MDCCLXIII
2. Если в числе есть 4 и / или 9 необходимо применить правило вычитания:
900 = 1000-100 = M - C = CM
--Ларионова Мария Олеговна 23:06, 31 октября 2012 (MSK)
Алфавитные система счисления
Позиционные системы счисления.
Позиционной системой счисления называется система счисления, в которой значение каждой цифры в изображении числа зависит от ее положения в ряду других цифр, изображающих число. Положение, занимаемой цифрой при письменном обозначении числа называется разрядом. Наша, естественная система счисления – десятичная – является позиционной. Это значит, что в числе 1978, цифра «1» – обозначает одну тысячу. Эта цифра стоит в позиции третьего разряда. Цифра «9» – девять сотен, второй разряд. Цифра «7» – семь десятков, первый разряд. А «8» – восемь единиц, нулевой разряд. Распишем вышесказанное в виде математической формулы: Файл:1 формула.jpg Распишем подобным образом дробное число: Файл:2 формула.jpg Очевидно, что в десятичной системе счисления числа 10^n, где n=(-∞;+∞),n – номер разряда, играют ключевую роль в формировании записи числа. Эти числа называются базисом десятичной системы счисления. Число 10 для нашей десятичной системы счисления является ее основанием. Оно показывает, что каждые десять единиц образуют один десяток, десять десятков образуют одну сотню, десять сотен образуют одну тысячу и т.д. В общем случае, для десятичной системы счисления, каждые десять единиц любого разряда образуют одну единицу соседнего, более старшего разряда. Базис системы счисления — это последовательность ключевых чисел, каждое из которых задает значение цифры в ее позиции или «вес» каждого разряда. Выбирая за основание системы счисления любое натуральное число k, то есть, считая, что k единиц любого разряда образует одну единицу соседнего более крупного разряда, придем к так называемой k-ичной системе счисления. Основные достоинства любой позиционной системы счисления:
ограниченное количество символов; простота выполнения арифметических операций. "Мысль выражать все числа немногими знаками, придавая им, кроме значения по форме, еще значения по месту, настолько проста, что именно из-за этой простоты трудно оценить, насколько она удивительна." Французский математик Пьер Симон Лаплас (1749-1827)
В повседневной жизни наиболее употребительна 10-ичная система счисления. И тем не менее великий французский математик Блез Паскаль писал:
"Десятичная система счисления построена довольно неразумно, конечно в соответствии с людскими обычаями, а вовсе не с требованиями естественной необходимости, как склонно думать большинство людей".
Десятичная система счисления характеризуется тем, что в ней считают десятками:
десять единиц это десяток; десять десятков это уже сотня; десять сотен тысяча и т.д.
Позиционные системы счисления обладают большими преимуществами в наглядности представления чисел и в простоте выполнения арифметических операций.
В позиционной системе счисления значение числа определяется не только набором входящих в него цифр, но и их местом (позицией) в последовательности цифр, изображающих это число, например, числа 127 и 721. Позиционной является десятичная система счисления, используемая в повседневной жизни. Количество символов, используемых в позиционной системе счисления, называется ее основанием. Его обозначают обычно буквой q. В десятичной системе счисления используется десять символов (цифр): 0, 1,2, 3, 4, 5, 6, 7, 8, 9, и основанием системы является число десять. Особое место среди позиционных систем счисления занимают системы со степенными весами разрядов, в которых веса смежных позиций цифр (разрядов) отличаются по величине в постоянное количество раз, равное основанию q системы счисления.
ПРИМЕРЫ:
1 — единичная (унарная) система счисления, может рассматриваться как вырожденный случай позиционной системы счисления[источник не указан 825 дней]. 2 — двоичная (в дискретной математике, информатике, программировании) 3 — троичная система счисления 4 — четверичная система счисления 8 — восьмеричная (в программировании) 10 — десятичная система счисления 12 — двенадцатеричная (широко использовалась в древности, в некоторых частных областях используется и сейчас) 16 — шестнадцатеричная (наиболее распространена в программировании, а также в шрифтах) 40 — сорокаичная система счисления (применялась в древности: в частности, «сорок сороков» = 1600) 60 — шестидесятеричная (измерение углов и, в частности, долготы и широты, измерение времени)
Перевод в десятичную систему счисления
Если число в b-ричной системе счисления равно
a_{n-1}\;a_{n-2}\ldots \;a_1\;a_0,
то для перевода в десятичную систему вычисляем такую сумму:
\sum_{k=0}^{n-1} a_k\cdot b^k
или, в более наглядном виде:
a_{n-1}\cdot b^{n-1} + a_{n-2} \cdot b^{n-2} + \ldots + a_1 \cdot b^1 + a_0 \cdot b^0,
либо, наконец, в виде схемы Горнера:
((\ldots(a_{n-1} \cdot b + a_{n-2}) \cdot b + a_{n-3}) \ldots ) \cdot b + a_0.
Например:
1011002 =
= 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 0 · 20 =
= 1 · 32 + 0 · 16 + 1 · 8 + 1 · 4 + 0 · 2 + 0 · 1 =
= 32 + 8 + 4 + 0 = 4410
Перевод из десятичной системы счисления
Целая часть
Последовательно делить целую часть десятичного числа на основание, пока десятичное число не станет равно нулю. Полученные при делении остатки являются цифрами нужного числа. Число в новой системе записывают, начиная с последнего остатка.
Дробная часть
Дробную часть десятичного числа умножаем на основание системы, в которую требуется перевести. Отделяем целую часть. Продолжаем умножать дробную часть на основание новой системы, пока она не станет равной 0. Число в новой системе составляют целые части результатов умножения в порядке, соответствующем их получению.
Пример
44_{10} переведём в двоичную систему:
44 делим на 2. частное 22, остаток 0 22 делим на 2. частное 11, остаток 0 11 делим на 2. частное 5, остаток 1
5 делим на 2. частное 2, остаток 1 2 делим на 2. частное 1, остаток 0 1 делим на 2. частное 0, остаток 1
Частное равно нулю, деление закончено. Теперь записав все остатки снизу вверх получим число 101100_2 Перевод из двоичной в восьмеричную и шестнадцатеричную системы
Для этого типа операций существует упрощённый алгоритм.
Для восьмеричной — разбиваем переводимое число на количество цифр, равное степени 2 (2 возводится в ту степень, которая требуется, чтобы получить основание системы, в которую требуется перевести (2³=8), в данном случае 3, то есть триад). Преобразуем триады по таблице триад:
000 0 100 4 001 1 101 5 010 2 110 6 011 3 111 7
Для шестнадцатеричной — разбиваем переводимое число на количество цифр, равное степени 2 (2 возводится в ту степень, которая требуется, чтобы получить основание системы, в которую требуется перевести (24=16), в данном случае 4, то есть тетрад). Преобразуем тетрады по таблице тетрад:
0000 0 0100 4 1000 8 1100 C 0001 1 0101 5 1001 9 1101 D 0010 2 0110 6 1010 A 1110 E 0011 3 0111 7 1011 B 1111 F
Пример:
преобразуем 1011002 восьмеричная — 101 100 → 548 шестнадцатеричная — 0010 1100 → 2C16
Перевод из восьмеричной и шестнадцатеричной систем в двоичную
Для этого типа операций существует упрощённый алгоритм-перевёртыш.
Для восьмеричной — преобразуем по таблице в триплеты
0 000 4 100 1 001 5 101 2 010 6 110 3 011 7 111
Для шестнадцатеричной — преобразуем по таблице в квартеты
0 0000 4 0100 8 1000 C 1100 1 0001 5 0101 9 1001 D 1101 2 0010 6 0110 A 1010 E 1110 3 0011 7 0111 B 1011 F 1111
Пример:
преобразуем 548 → 101 100 2C16 → 0010 1100
Перевод из двоичной системы в 8- и 16-ричную
Перевод дробной части из двоичной системы счисления в системы счисления с основаниями 8 и 16 осуществляется точно также, как и для целых частей числа, за тем лишь исключением, что разбивка на октавы и тетрады идёт вправо от десятичной запятой, недостающие разряды дополняются нулями справа. Например, рассмотренное выше число 1100,0112 будет выглядеть как 14,38 или C,616. Перевод из произвольной системы счисления в десятичную
Рассмотрим пример перевода двоичного числа 1100,0112 в десятичное. Целая часть этого числа равна 12 (см. выше), а вот перевод дробной части рассмотрим подробнее:
0,011 = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} = 0 + 0,25 + 0,125 = 0,375.
Итак, число 1100,0112 = 12,37510.
Точно также осуществляется перевод из любой системы счисления, только вместо «2» ставится основание системы.
Для удобства перевода, целую и дробную части числа переводят отдельно, а результат потом конкатенируют. Перевод из десятичной системы в произвольную
Для перевода дробной части числа в другие системы счисления нужно обратить целую часть в нуль и начать умножение получившегося числа на основание той системы, в которую нужно перевести. Если в результате умножения будут снова появляться целые части, их нужно повторно обращать в нуль, предварительно запомнив (записав) значение получившейся целой части. Операция заканчивается, когда дробная часть полностью обратится в нуль. Ниже приводится пример перевода числа 103,62510 в двоичную систему счисления.
Переводим целую часть по правилам, описанным выше, получаем 10310 = 11001112.
0,625 умножаем на 2. Дробная часть 0,250. Целая часть 1. 0,250 умножаем на 2. Дробная часть 0,500. Целая часть 0. 0,500 умножаем на 2. Дробная часть 0,000. Целая часть 1.
Итак, сверху вниз получаем число 1012. Поэтому 103,62510 = 1100111,1012
Точно также осуществляется перевод в системы счисления с любым основанием.
Сразу нужно отметить, что этот пример специально подобран, в общем случае очень редко удаётся завершить перевод дробной части числа из десятичной системы в другие системы счисления, а потому, в подавляющем большинстве случаев, перевод можно осуществить с какой либо долей погрешности. Чем больше знаков после запятой — тем точнее приближение результата перевода к истине. В этих словах легко убедиться, если попытаться, например, перевести в двоичный код число 0,626.
Перевод целых чисел из 10-ой системы счисления в систему счисления с основанием q.
Перевод целых чисел из систем счисления с основанием q в 10-ую систему счисления.
Для перевода числа в десятичную систему счисления из системы счисления с другим основанием каждый коэффициент переводимого числа умножается на основание системы в степени соответствующей этому коэффициенту и полученные результаты складываются.
Перевод целых чисел в десятичную систему счисления
Для перевода двоичного числа в десятичное необходимо это число представить в виде суммы произведений степеней основания двоичной системы счисления на соответствующие цифры в разрядах двоичного числа.
Примеры:
Основание системы выделены в круглых скобках, степени в квадратных.
X(2)=A(n)*2[n-1]+A(n-1)*2[n-2]+A(n-2)*2[n-3]+...+A(2)*A[1]+A(1)*2(0)
1)Например, требуется перевести двоичное число 10110110 в десятичное. В этом числе 8 цифр и 8 разрядов ( разряды считаются, начиная с нулевого, которому соответствует младший бит). В соответствии с уже известным нам правилом представим его в виде суммы степеней с основанием 2:
При переводе удобно пользоваться таблицей степеней двойки: Файл:CKAGdwK5-Po.jpg
Из этого примера видно, в частности, что десятичная система счисления более компактно отображает числа - 3 цифры (т.е. бита) вместо 8 цифр в двоичной системе счисления. Для вычислений "вручную" и решения примеров и контрольных заданий вам могут пригодиться таблицы степеней оснований изучаемых систем счисления (2, 8, 10, 16).
X(8)=A(n)*8[n-1]+A(n-1)*8[n-2]+A(n-2)*8[n-3]+...+A(2)*8[1]+A(1)*8[0]
2)Дано число 327(8), которое надо перевести в 10-ную систему счисления.
Для этого представим наше число в виде суммы произведений соответствующих цифр числа и степеней основания 8.
327(8)=3*8[2]+2*8[1]+7*8[0] = 3*64+2*8+7*1=192*16+7=21510
т.е.
327(8) = 215(10)
При переводе удобно пользоваться таблицей степеней восьмёрки:
3)Число A1D516 перевести в10 систему счисления.
A1D5 = A*16[3]+1*16[2]+D*16[1]+5*16[0]
При переводе удобно пользоваться таблицей степеней числа 16:
Тогда A*16[3]+1*16[2]+D*16[1]+5*16[0] = 10 *16[3]+1*16[2]+13*16[1]+5*16[0]= 10*4096 +1* 256 + 13*16 + 5*1= =40960+256+208+5 = 41429(10)
т.е. A1D516 = 41429(10)
Перевод дробных чисел в десятичную систему счисления
Вспомним правила перевода в десятичную систему счисления:
11010(2) = 1*2[4] + 1*2[3] + 0*2[2] +1*2[1]+ 0*2[0] = 1*16 + 1*8 + 0*4 + 1*2 + 0*1 = 16 + 8 +0 + 2 +0 = 26(10)
И применим некоторую особенность уравновешенной системы, в которой ноль является как бы основой в чашечных весах, а дальше знаки, как гирьки: 1 и -1, 2 и -2, … Так и здесь, но со степенями: как только дошли до нулевой степени, начинается обратные отсчет степеней, т.е. степени -1, -2, -3 и т.д. Получаем:
11010,101(2)= 1*2[4] + 1*2[3] + 0*2[2] +1*2[1] + 0*2[0] + 1*2[-1]+ 0*2[-2] + 1*2[-3]=26,625(10)
Напоминаю, что нули можно пропускать , поэтому запись может быть сразу проще:
11010,101(2)= 1*2[4] + 1*2[3] + 1*2[1] + 1*2[-1]+ 1*2[-3]=26,625(10)
Арифметические операции в позиционных системах счисления.
Двоичное кодирование графической, текстовой и звуковой информации
Информация, выраженная с помощью естественных и формальных языков в письменной форме, обычно называется текстовой информацией.
Для представления текстовой информации (прописные и строчные буквы русского и латинского алфавитов, цифры, знаки и математические символы) достаточно 256 различных знаков. По формуле можно вычислить, какое количество информации необходимо, чтобы закодировать каждый знак:
N = 2i => 256 = 2i => 28 = 2i => I = 8 битов.
Для обработки текстовой информации на компьютере необходимо представить ее в двоичной знаковой системе. Для кодирования каждого знака требуется количество информации, равное 8 битам, т. е. длина двоичного кода знака составляет восемь двоичных знаков. Каждому знаку необходимо поставить в соответствие уникальный двоичный код из интервала от 00000000 до 11111111 (в десятичном коде от 0 до 255) (табл. 3.1).
Человек различает знаки по их начертанию, а компьютер - по их двоичным кодам. При вводе в компьютер текстовой информации происходит ее двоичное кодирование, изображение знака преобразуется в его двоичный код. Пользователь нажимает на клавиатуре клавишу со знаком, и в компьютер поступает определенная последовательность из восьми электрических импульсов (двоичный код знака). Код знака хранится в оперативной памяти компьютера, где занимает одну ячейку.Таблица 3.1. Кодировки знаков
В процессе вывода знака на экран компьютера производится обратное перекодирование, т. е. преобразование двоичного кода знака в его изображение.
Различные кодировки знаков. Присваивание знаку конкретного двоичного кода - это вопрос соглашения, которое фиксируется в кодовой таблице. В существующих кодовых таблицах первые 33 кода (десятичные коды с 0 по 32) соответствуют не знакам, а операциям (перевод строки, ввод пробела и т. д.).
Десятичные коды с 33 по 127 являются интернациональными и соответствуют знакам латинского алфавита, цифрам, знакам арифметических операций и знакам препинания.
Десятичные коды с 128 по 255 являются национальными, т. е. в различных национальных кодировках одному и тому же коду соответствуют разные знаки. К сожалению, в настоящее время существуют пять различных кодовых таблиц для русских букв (Windows, MS-DOS, КОИ-8, Mac, ISO (табл. 3.1 и 3.2)), поэтому тексты, созданные в одной кодировке, не будут правильно отображаться в другой.Таблица 3.2. Десятичные коды некоторых символов в различных кодировках
Например, в кодировке Windows последовательность числовых кодов 221, 194, 204 образует слово "ЭВМ", тогда как в других кодировках это будет бессмысленный набор символов.
К счастью, в большинстве случаев пользователь не должен заботиться о перекодировках текстовых документов, так как это делают специальные программы-конверторы, встроенные в операционную систему и приложения.
В последние годы широкое распространение получил новый международный стандарт кодирования текстовых символов Unicode, который отводит на каждый символ 2 байта (16 битов).
По формуле можно определить количество символов, которые можно закодировать согласно этому стандарту:
N = 2i = 216 = 65 536.
Такого количества символов оказалось достаточно, чтобы закодировать не только русский и латинский алфавиты, цифры, знаки и математические символы, но и греческий, арабский, иврит и другие алфавиты.
Кодирование звуковой информации
Аналоговая и цифровая информация
Физически звук представляет собой волновые колебания давления в той или иной среде. звук представляет собой нечто неделимое на части (непрерывное), пробегающее в пространстве и времени. Чтобы записать звук на какой-нибудь носитель можно соотнести его уровень (силу) с какой-нибудь измеряемой характеристикой этого носителя. Звук можно хранить в так называемой аналоговой форме, когда значения изменяются непрерывно (плавно), что близко к естественному звуку.
Звук в компьютере хранится как и любая информация в цифровой форме. Данные должны быть представлены числами, а, следовательно, информация в компьютере дискретна (разделена). Для того, чтобы записать звук на цифровой носитель информации (например, жесткий диск), его подвергают так называемой оцифровке, механизм которой заключается в измерении параметров звука через определенные промежутки времени (очень малые).
Дискретизация и квантование При преобразовании звуковой информации в цифровую форму ее подвергают дискретизации и квантованию. Дискретизация заключается в замерах величины аналогового сигнала огромное множество раз в секунду. Полученной величине аналогового сигнала сопоставляется определенное значение из заранее выделенного диапазона: 256 (8 бит) или 65536 (16 бит). Привидение в соответствие уровня сигнала определенной величине диапазона и есть квантование. чем чаще мы проводим замеры, тем точнее будет соответствовать цифровой звук своему аналоговому оригиналу .Также, чем больше бит отведено под кодирование уровня сигнала (квантование), тем точнее соответствие. звук хорошего качества будет содержать больше данных и, следовательно, больше занимать места на цифровом носителе информации. Файл:Sound.preview.jpg --Шатрюк Людмила К. 19:17, 14 ноября 2012 (MSK)
Источники информации
Информация в живой и неживой природе. Свойства информации:
Алфавитный и содержательный подходы к измерению информации:
Единицы измерения информации:
История чисел и систем счисления. Непозиционные системы счисления: Викизнание [1] Википедия [2] Сайт учителя информатики Эфендиева М.Ж [3]
Позиционные системы счисления:
Перевод целых чисел из 10-ой системы счисления в систему счисления с основанием q:
Перевод целых чисел из систем счисления с основанием q в 10-ую систему счисления:
Арифметические операции в позиционных системах счисления:
Двоичное кодирование графической, тестовой и звуковой информации: Сайт учителя информатики Савенковой Т.Н. [4]
