Основи програмування

1. Розробити блок-схему алгоритму розв’язку завдання, згідно свого варіанту.
2. Написати код програми для розв’язку поставленого завдання на мові С.
3. Оформити звіт по роботі. Звіт повинен містити тему та мету роботи, код написаної програми та блок-схему алгоритму.

Індивідуальне завдання

Простий рівень

Стверджується, що Цезар використовував для «шифрування» конфіденційних повідомлень зміщення кожної літери на певну кількість позицій. Наприклад, він міг написати A як B, B як C, C, як D, ..., і, пройшовши весь алфавіт, Z як A. Так, щоб сказати комусь HELLO, Цезар міг написати IFMMP. Отримавши такі повідомлення від Цезаря, отримувачам доведеться «розшифрувати» їх, замінюючи літери у протилежному напрямку з тим же зміщенням.

Таємність цієї «криптосистеми» опиралася лише на Цезаря та на отримувачів, що знали ключ, кількість позицій, на яку Цезар змістив свої літери (табл. 4.1). Не особливо безпечно за сучасними стандартами, але як для одного з перших у світі методів шифрування – цілком достатньо.

Незашифрований текст зазвичай називається відкритим текстом. Зашифрований текст зазвичай називається шифрованим текстом.

 

Таблиця 4.1 – Шифрування тексту «HELLO» з ключем 1

 

У загальному випадку, алгоритм Цезаря (тобто шифр) кодує повідомлення, «провертаючи» кожну літеру на k позицій. Якщо p – це відкритий текст (тобто незашифроване повідомлення), p_i – це i-й символ у p, а k – секретний ключ (тобто невід’ємне ціле число), тоді кожна літера c_i у зашифрованому тексті c, обчислюється як

c_i = (p_i + k) mod 26

де mod 26 означає «залишок від ділення на 26».

Завдання: написати програми, яка шифрує повідомлення за допомогою шифру Цезаря.

Програма повинна прийняти єдиний аргумент командного рядка –  невід'ємне ціле число (k).

Якщо програма виконується без аргументів командного рядка або з кількома аргументами, програма повинна видати повідомлення про помилку.

Припустимо, що користувач в якості аргументу командного рядка буде вводити невід'ємним ціле число.

Програма повинна вивести надпис «Відкритий текст: » та запропонувати користувачеві ввести рядок тексту (використовуючи get_string).

Програма повинна вивести надпис «Шифрований текст: », за яким буде виведено відповідний шифрований текст відкритого тексту, причому неалфавітні символи повинні виводитися без змін.

Програма повинна також зберегти регіст літер: великі літери залишаються великими, малі – малими.

 

Складний рівень

Шифр Віженера покращує шифр Цезаря шляхом шифрування повідомлень за допомогою послідовності ключів (ключовим словом). Іншими словами, якщо p – це деякий простий текст і k – це ключове слово (тобто алфавітний рядок, в якому A являє собою 0, B позначає 1, C – 2, ..., а Z представляє 25), тоді кожна літера c_i в шифрованому тексті c, обчислюється як:

c_i = (p_i + k_j) mod 26

де k_j j-та літера ключового слова k. І якщо k коротше, ніж p, то літери в k повинні бути повторно використані циклічно стільки разів, скільки потрібно для шифрування р.

 

Таблиця 4.2 – Шифрування тексту «HELLO» з ключовим словом ABC

 

Завдання: написати програми, яка шифрує повідомлення за допомогою шифру Віженера.

Якщо програма виконується без аргументів командного рядка або з кількома аргументами, програма повинна видати повідомлення про помилку.

Програма повинна прийняти єдиний аргумент командного рядка: ключове слово, k, що складається з алфавітних символів.

Програма повинна вивести надпис «Відкритий текст: » та запропонувати користувачеві ввести рядок тексту (використовуючи get_string).

Програма повинна вивести надпис «Шифрований текст: », за яким буде виведено відповідний шифрований текст відкритого тексту, причому неалфавітні символи повинні виводитися без змін.

Програма повинна також зберегти регіст літер: великі літери залишаються великими, малі – малими.

 

Рівень підвищеної складності

У більшості Linux-систем є файл /etc/shadow, в якому містяться імена користувачів та їх паролі. Однак паролі в них не зберігаються «в чистому» вигляді, а шифруються за допомогою «односторонньої хеш-функції». Коли користувач входить до цих систем, набравши ім’я користувача та пароль, останній шифрується з тією ж хеш-функцією, і результат порівнюється з записом користувача /etc/shadow. Якщо два хеші збігаються, користувач отримує доступ. Якщо користувач забуває пароль – технічна підтримка не може вказати цей пароль, але може змінити його. Це все тому, що технічна підтримка може лише побачити хеш паролю, але не сам пароль. Але вони можуть створити новий хеш.

Хоча паролі в /etc/shadow хешовані, нерідко зловмисники, отримавши цей файл певним чином, можуть вгадати (і перевірити) паролі користувачів або зламати їх за допомогою грубої сили (тобто намагаючись перебрати всі можливі паролі). Нижче наведено приклад, як /etc/shadow може виглядати, хоча і в спрощеному вигляді, де кожен рядок показує ім’я користувача і хеш:

andi:50.jPgLzVirkc

jason:50YHuxoCN9Jkc

malan:50QvlJWn2qJGE

mzlatkova:50CPlMDLT06yY

patrick:50WUNAFdX/yjA

rbowden:50fkUxYHbnXGw

summer:50C6B0oz0HWzo

stelios:50nq4RV/NVU0I

wmartin:50vtwu4ujL.Dk

zamyla:50i2t3sOSAZtk

 

Завдання: написати програму, яка зламує паролі, закодовані хеш-функцією.

Програма повинна прийняти єдиний аргумент командного рядка: хешований пароль.

Якщо програма виконується без аргументів командного рядка або з кількома аргументами, програма повинна видати повідомлення про помилку.

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

Припустимо, що кожен пароль було хешовано за допомогою функції сrypt на базі алгоритму DES (потрібно підключити crypt.h). Функція має 2 аргументи: key та salt. Де key – текст, який кодується; salt – перші два символи хешу.

Припустимо, що кожен пароль не перевищує чотирьох символів та складається лише з великих та/або малих літер.