Wiki ТНТУ - Внесок користувача [uk]

Асиметричні алгоритми кодування

2011-05-12T11:28:58Z

Natal ka: перейменував «Асиметричні криптосистеми» на «Асиметричні алгоритми кодування»

'''Асиметричні алгоритми шифрування''' — алгоритми шифрування, які використовують різні (і такі які [[важко обчислити]] один з одного) [[ключ]]і для [[шифрування]] та [[розшифрування]] даних.

'''Асиметричні криптосистеми''' — ефективні системи криптографічного захисту даних, які також називають криптосистемами з відкритим ключем. В таких системах для зашифровування даних використовується один ключ, а для розшифровування — інший [[ключ]] (звідси і назва — асиметричні). Перший ключ є відкритим і може бути опублікованим для використання усіма користувачами системи, які шифрують дані. Розшифровування даних за допомогою відкритого ключа неможливе. Для розшифровування даних отримувач зашифрованої інформації використовує другий ключ, який є секретним. Зрозуміло, що ключ розшифровування не може бути визначеним з ключа зашифровування.

Головне досягнення асиметричного шифрування в тому, що воно дозволяє людям, що не мають існуючої домовленості про безпеку, обмінюватися секретними повідомленнями. Необхідність відправникові й одержувачеві погоджувати [[таємний ключ]] по спеціальному захищеному каналі цілком відпала. Прикладами криптосистем з відкритим ключем є [[Elgamal]] (названа на честь автора, Тахіра Ельгамаля), [[RSA]] (названа на честь винахідників: Рона Рівеста, Аді Шаміра і Леонарда Адлмана), [[Diffie-Hellman]] і [[DSA]], Digital Signature Algorithm (винайдений Девідом Кравіцом).

== Історія ==
Історія криптографії налічує близько 4 тисяч років. В якості основного критерію періодизації криптографії можливо використовувати технологічні характеристики використовуваних методів шифрування.

Перший період (приблизно з третього тисячоліття до н. Е..) Характеризується пануванням моноалфавітних шифрів (основний принцип — заміна алфавіту вихідного тексту іншим алфавітом через заміну літер іншими літерами або символами). Другий період (хронологічні рамки — з IX століття на Близькому Сході (Ал-Кінді) і з XV століття в Європі ([[Леон Баттіста Альберті]]) — до початку XX століття) ознаменувався введенням в обіг поліалфавітних шифрів. Третій період (з початку і до середини XX століття) характеризується впровадженням електромеханічних пристроїв в роботу шифрувальників. При цьому продовжувалося використання поліалфавітних шифрів.

== Принцип роботи ==
Початок асиметричним шифру було покладено в роботі «Нові напрямки в сучасній криптографії» [[Уітфілд Діффі]] та [[Мартіна Хеллмана]], опублікованій в 1976 році. Перебуваючи під впливом роботи Ральфа Меркле (Ralph Merkle) про поширення відкритого ключа, вони запропонували метод отримання секретних ключів, використовуючи відкритий канал. Цей метод експоненціального обміну ключів, який став відомий як обмін ключами Діффі-Хеллмана, був першим опублікованим практичним методом для встановлення поділу секретного ключа між завіреними користувачами каналу. У 2002 році Хеллмана запропонував називати даний алгоритм «Діффі — Хеллмана — Меркле», визнаючи внесок Меркле в винахід криптографії з відкритим ключем. Ця ж схема була розроблена Малькольмом Вільямсоном в 1970-х, але трималася в секреті до 1997 року. Метод Меркле з розповсюдження відкритого ключа був винайдений в 1974 році і опублікований в 1978, його також називають загадкою Меркле.

У 1977 році вченими Рональдом Рівестом (Ronald Linn Rivest), Аді Шамір (Adi Shamir) і Леонардом Адлеманом (Leonard Adleman) з [[Массачусетського Технологічного Інституту]] (MIT) був розроблений алгоритм шифрування, заснований на проблемі про розкладанні на множники. Система була названа за першими літерами їхніх прізвищ. Ця ж система була винайдена Клиффордом Коксом (Clifford Cocks) в 1973 році, що працював в центрі урядового зв'язку (GCHQ). Але ця робота зберігалася лише у внутрішніх документах центру, тому про її існування було не відомо до 1977 року. RSA став першим алгоритмом, придатним і для шифрування, і для цифрового підпису.

== Криптографія з відкритим ключем ==
Проблема керування ключами була вирішена криптографією з відкритим, або асиметричним, ключем, концепція якої була запропонована Уітфілдом Діффі і Мартіном Хеллманом у 1975 році.
Криптографія з відкритим ключем — це асиметрична схема, у якій застосовуються пари ключів: відкритий (public key), що зашифровує дані, і відповідний йому закритий (private key), що їх розшифровує. Ви поширюєте свій відкритий ключ по усьому світу, у той час як закритий тримаєте в таємниці. Будь-яка людина з копією вашого відкритого ключа може зашифрувати [[інформація|інформацію]], що тільки ви зможете прочитати. Хто завгодно. Навіть люди, з якими ви ніколи не зустрічалися.

Хоча ключова пара математично зв'язана, обчислення закритого ключа з відкритого в практичному плані нездійсненна. Кожний, у кого є відкритий ключ, зможе зашифрувати дані, але не зможе їх розшифрувати. Тільки людина, яка володіє відповідним закритим ключем може розшифрувати [[інформація|інформацію]].

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

=== Ідея створення ===
Ідея криптографії з відкритим ключем дуже тісно пов'язана з ідеєю [[односторонніх функцій]], тобто таких функцій f (x), що за відомим x досить просто знайти значення f (x), тоді як визначення x з f (x) складно в сенсі теорії.

Але сама одностороння функція марна в застосуванні: нею можна [[зашифрувати]] повідомлення, але [[розшифрувати]] не можна. Тому криптографія з відкритим ключем використовує односторонні функції з лазівкою. Лазівка — це якийсь секрет, який допомагає розшифрувати. Тобто існує такий y, що знаючи f (x), можна обчислити x. Приміром, якщо розібрати годинник на безліч складових частин, то дуже складно зібрати знову працюючий годинник. Але якщо є інструкція по зборці (лазівка), то можна легко вирішити цю проблему.

== Дивіться також ==
* [[Симетричне шифрування]]
* [[RSA]]

Асиметричні криптосистеми

2011-05-12T11:28:58Z

Natal ka: перейменував «Асиметричні криптосистеми» на «Асиметричні алгоритми кодування»

#ПЕРЕНАПРАВЛЕННЯ [[Асиметричні алгоритми кодування]]

Транспортне кодування

2011-05-12T11:27:30Z

Natal ka: Створена сторінка: '''Транспортне кодування''' - в криптографії використовується додаткове кодування для сум…

'''Транспортне кодування''' - в криптографії використовується додаткове кодування для сумісності з протоколами передачі даних.
Мета кодування - виключити появу у вихідному потоці перших 32 символів [[ASCII]] набору та інших службових символів.
Способи реалізації можуть бути різними. Часто використовується система Base64 (стандарт - RFC1251), розроблена для мережі Інтернет.

Атака Man-in-the-Middle

2011-05-12T11:22:47Z

Natal ka: Створена сторінка: '''Атака «людина посередині»''' (англ: Man-in-the-Middle, MitM-атака) - термін у криптографії, що позн…

'''Атака «людина посередині»''' (англ: Man-in-the-Middle, MitM-атака) - термін у [[криптографії]], що позначає ситуацію, коли атакуючий здатний читати і видозмінювати по своїй волі повідомлення, якими обмінюються кореспонденти, причому жоден з останніх не може здогадатися про його присутності в каналі.
Метод компрометації каналу зв'язку, при якому зломщик, підключившись до каналу між контрагентами, здійснює активне втручання в протокол передачі, видаляючи, спотворюючи інформацію або нав'язуючи хибну.

==Принцип атаки==
Припустимо, об'єкт A планує передати об'єкту B якусь інформацію. Об'єкт C володіє знаннями про структуру і властивості використовуваного методу передачі даних, а також про факт планованої передачі власне інформації, яку З планує перехопити. Для здійснення атаки З «видається» об'єкту А як В, а об'єкту В - як А. Об'єкт А, помилково вважаючи, що він направляє інформацію В, посилає її об'єкту С. Об'єкт С, отримавши інформацію, і зробивши з неї деякі дії (наприклад , скопіювавши або модифікувавши у своїх цілях) пересилає дані власне одержувачу - В; об'єкт В, у свою чергу, вважає, що інформація була отримана ним безпосередньо від А.

==Реалізація та протидію==
Подібний тип атак використовується в деяких програмних продуктах для прослуховування мережі, наприклад Шаблон: Не перекладено 3.
Для запобігання атак подібного типу абонентам A і B досить за допомогою достовірного каналу передати один одному цифрові підписи публічних ключів шифрування. Тоді при порівнянні підписів ключів у сеансах шифрування можна буде встановити, яким ключем шифрувалися дані, і не відбулася чи підміна ключів.
==Приклад в літературі==
Наочний літературний приклад можна побачити в «Казці про царя Салтана» Пушкіна, де фігурують три «людини посередині»: ткаля, кухарка і Бабаріха. Саме вони підміняють листи, адресовані царя, і його відповідь кореспонденцію.

Алгоритм RSA

2011-05-12T00:53:13Z

Natal ka: Створена сторінка: '''RSA''' — криптографічна система з відкритим ключем. RSA став першим алгори…

'''RSA''' — [[шифрування|криптографічна]] система з відкритим ключем.

RSA став першим алгоритмом такого типу, придатним і для [[шифрування]] і для [[цифровий підпис|цифрового підпису]]. Алгоритм використовується у великій кількості криптографічних [[застосунок|застосунків]].

== Історія ==
Опис RSA було опубліковано у [[1977]] році [[Райвест, Рональд|Рональдом Райвестом]] (Ronald Linn Rivest), [[Шамір, Аді|Аді Шаміром]] (Adi Shamir) і [[Адлеман, Леонард|Леонардом Адлеманом]] (Leonard Adleman) з Масачусетського Технологічного Інституту (MIT).

Британський математик [[Кліфорд Кокс]] (Clifford Cocks), що працював в [[GCHQ|центрі урядового зв'язку]] (GCHQ) [[Великобританія|Великобританії]], описав аналогічну систему в [[1973]] році у внутрішніх документах центру, але ця робота не була розкрита до [[1997]] року, тож Райвест, Шамір і Адлеман розробили RSA незалежно від роботи Коксу.

В [[1983]] році був виданий [http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US4405829 патент 4405829] США, термін дії якого минув 21 вересня 2000 року.

== Опис алгоритму ==
Безпека алгоритму RSA побудована на принципі складності [[Факторизація|факторизації]]. Алгоритм використовує два [[Ключі (криптографія)|ключі]] — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.

=== Генерація ключів ===
Для того, щоб згенерувати пари ключів виконуються такі дії:

# вибираються два великих [[просте число|простих числа]] <math>p\,</math> и <math>q\,</math>
# обчислюється їх добуток <math>n=pq \,</math>
# обчислюється [[Функція Ейлера]] <math>\varphi(n)=(p-1)(q-1)</math>
# вибирається ціле <math>e\,</math> таке, що <math>1<e<\varphi(n)</math> та <math>e\,</math> [[взаємно прості числа|взаємно просте]] з <math>\varphi(n)</math>
# за допомогою [[Алгоритм Евкліда|розширеного алгоритма Евкліда]] знаходиться число <math>d\,</math> таке, що <math>ed\equiv 1\pmod{\varphi(n)}</math>

Число <math>n\,</math> називається модулем, а числа <math>e\,</math> і <math>d\,</math> — відкритою й секретною експонентами, відповідно. Пари чисел <math>(n,\,e)</math> є відкритою частиною ключа, а <math>(n,\,d)</math> — секретною. Числа <math>p\,</math> і <math>q\,</math> після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.

=== Шифрування й розшифрування ===
Для того, щоб зашифрувати повідомлення <math>m<n\,</math> обчислюється
: <math>c=m^e\bmod\,n \,</math>.
Число <math>c\,</math> і використовується в якості шифртексту.
Для розшифрування потрібно обчислити
: <math>m=c^d\bmod\,n \,</math>.
Неважко переконатися, що при розшифруванні ми відновимо вихідне повідомлення:

: <math>c^d\equiv (m^e)^d\equiv m^{ed}\pmod n\,</math>

З умови

: <math>ed\equiv 1\pmod{\varphi(n)}</math>

виходить, що

: <math>ed=k\varphi(n)+1</math> для деякого цілого <math>k\,</math>, отже
: <math>m^{ed}\equiv m^{k\varphi(n)+1}\pmod n</math>

Згідно [[Теорема Ейлера|теореми Ейлера]]:
: <math>m^{\varphi(n)}\equiv 1\pmod n</math>,
тому
: <math>m^{k\varphi(n)+1}\equiv m \pmod n</math>
: <math>c^d\equiv m\pmod n\,</math>

=== Цифровий підпис ===
RSA може використовуватися не тільки для шифрування, але й для цифрового підпису. Підпис <math>s\,</math> повідомлення <math>m\,</math> обчислюється з використанням секретного ключа за формулою:
: <math>s=m^d\bmod\ n\,</math>
Для перевірки правильності підпису потрібно переконатися, що виконується рівність
: <math>m=s^e\bmod\ n\,</math>

== Деякі особливості алгоритму ==
=== Генерація простих чисел ===
Для знаходження двох великих [[просте число|простих чисел]] <math>p\,</math> і <math>q\,</math>, при генерації ключа, звичайно використовуються ймовірносні тести чисел на простоту, які дозволяють швидко виявити й відкинути [[складне число|складні числа]].

Для генерації <math>p\,</math> і <math>q\,</math> необхідно використовувати криптографічно надійний генератор випадкових чисел. У порушника не має бути можливості одержати будь-яку інформацію про значення цих чисел.

<math>p\,</math> і <math>q\,</math> не повинні бути занадто близькими одне до одного, інакше можна буде знайти їх використовуючи [[метод факторизації Ферма]]. Крім того, необхідно вибирати [[Сильне просте число|«сильні» прості числа]], щоб не можна було скористатися [[p-1 алгоритм Поларда|p-1 алгоритмом Поларда]].

=== Доповнення повідомлень ===
При практичному використанні необхідно деяким чином доповнювати повідомлення. Відсутність доповнень може призвести до деяких проблем:
* значення <math>m=0\,</math> і <math>m=1\,</math> дадуть при зашифруванні шифртексти 0 і 1 при будь-яких значеннях <math>e\,</math> і <math>n\,</math>.
* при малому значенні відкритого показника (<math>e=3\,</math>, наприклад) можлива ситуація, коли виявиться, що <math>m^e<n\,</math>. Тоді <math>c=m^e\bmod\ n=m^e\,</math>, і зловмисник легко зможе відновити вихідне повідомлення обчисливши корінь ступеня <math>e\,</math> з <math>c\,</math>.
* оскільки RSA є детермінованим алгоритмом, тобто не використовує випадкових значень у процесі роботи, то зловмисник може використати атаку з обраним відкритим текстом.

Для розв'язання цих проблем повідомлення доповнюються перед кожним зашифруванням деяким випадковим значенням. Доповнення виконується таким чином, щоб гарантувати, що <math>m\neq0\,</math>, <math>m\neq1\,</math> і <math>m^e>n\,</math>. Крім того, оскільки повідомлення доповнюється випадковими даними, то зашифровуючи той самий відкритий текст ми щораз будемо одержувати інше значення шифртексту, що робить атаку з обраним відкритим текстом неможливою.

=== Вибір значення відкритого показника ===
RSA працює значно повільніше симетричних алгоритмів. Для підвищення швидкості шифрування відкритий показник <math>e\,</math> вибирається невеликим, звичайно 3, 17 або 65537. Ці числа у двійковому вигляді містять тільки по двох одиниці, що зменшує число необхідних операцій множення при піднесенні до степеня. Наприклад, для піднесення числа <math>m\,</math> до степеня 17 потрібно виконати тільки 5 операцій множення:
: <math>m^2= m\cdot m</math>
: <math>m^4=m^2\cdot m^2</math>
: <math>m^8=m^4\cdot m^4</math>
: <math>m^{16}=m^8\cdot m^8</math>
: <math>m^{17}=m^{16}\cdot m</math>

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

=== Вибір значення секретного показника ===
Значення секретного показника <math>d\,</math> повинне бути досить великим. У [[1990]] році Міхаель Вінер (Michael J. Wiener) показав, що якщо <math>q<p<2q\,</math> і <math>d<n^{\frac14}/3</math>, то є ефективний спосіб обчислити <math>d\,</math> по <math>n\,</math> і <math>e\,</math>. Однак, якщо значення <math>e\,</math> вибирається невеликим, те <math>d\,</math> виявляється досить великим і проблеми не виникає.

== Довжина ключа ==
Число ''n'' повинне мати розмір не менше 512 біт. У даний момент (2007 рік) система шифрування на основі RSA вважається надійною, починаючи з величини N в 1024 біта.

== Застосування RSA ==
Система RSA використовується для захисту програмного забезпечення й у схемах [[цифровий підпис|цифрового підпису]].
Також вона використовується у відкритій системі шифрування [[PGP]].

Через низьку швидкість шифрування (близько 30 кбіт/сек при 512 бітному ключі на процесорі 2 ГГц), повідомлення звичайно шифрують за допомогою більш продуктивних [[симетричний алгоритм шифрування|симетричних алгоритмів]] з випадковим ключем (''сеансовий ключ''), а за допомогою RSA шифрують лише цей ключ.

Асиметричні алгоритми кодування

2011-05-12T00:51:28Z

Natal ka: Створена сторінка: '''Асиметричні алгоритми шифрування''' — алгоритми шифрування, які використовують різн…

Мережева безпека

2011-05-12T00:47:56Z

Natal ka: Створена сторінка: '''Мережева безпека''' – це комплекс заходів, спрямованих на захист мереж від атак і несанк…

'''Мережева безпека''' – це комплекс заходів, спрямованих на захист мереж від атак і несанкціонованого доступу. Захист мережі забезпечується як програмними, так і апаратними засобами.

Скремблери

2011-05-12T00:44:12Z

Natal ka: Створена сторінка: '''Скремблер''' (англ. ''scrambled'' - зашифрований) - програмне або апаратне пристрій (алгоритм),…

'''Скремблер''' (англ. ''scrambled'' - зашифрований) - програмне або апаратне пристрій ([[алгоритм]]), що виконує '''скремблювання'''.
'''Скремблювання''' - це оборотне перетворення цифрового потоку без зміни швидкості передачі з метою отримання властивостей випадкової послідовності. Після скремблювання поява «1» і «0» у вихідний послідовності рівноймовірні. Скремблювання - оборотний процес, тобто вихідне повідомлення можна відновити застосувавши зворотний алгоритм.

==Принцип роботи ==
Генерується псевдослучайная послідовність (однакова для скремблера і дескремблера) біт. Знову надходить у скремблер біт підсумовується по модулю два з бітом псевдовипадковою послідовності. Після чого біт відправляється на вихід, скремблер бере наступний вхідний біт псевдовипадковою і вхідної послідовності і повторює операцію. Таким чином, в простому випадку скремблер може бути зібраний на двох тактируемого регістрах зсуву з зворотними зв'язками і 2-х входові елемента «виключає або». Зворотне перетворення здійснюється в зворотному порядку. Псевдослучайная послідовність використовується циклічно. Скремблювання застосовується в багатьох сучасних системах цифрового зв'язку ([[SDH]])
== Відмінність від шифрування ==
Скремблювання - приватний випадок шифрування. З появою блокових алгоритмів шифрування актуальність скремблера втрачена. На даний момент у скремблера основне завдання - надання послідовності біт псевдовипадкового характеру.
== Див. також ==
[[Кодування]].
[[Шифрування]].
[[Стиснення]].
[[Криптографія]].

Термінальний сервер

2011-05-12T00:35:03Z

Natal ka:

'''Термінальний сервер''', ''сервер терміналів'' (англ. ''terminal server'') - сервер, що надає клієнтам обчислювальні ресурси (процесорний час, пам'ять, дисковий простір) для вирішення завдань. Технічно, '''термінальний сервер''' являє собою дуже потужний комп'ютер (або кластер), з'єднаний по мережі з термінальними клієнтами - які, як правило, являють собою малопотужні або застарілі робочі станції або спеціалізовані рішення для доступу до термінального сервера. Термінальний сервер служить для віддаленого обслуговування користувача з наданням робочого столу.

== Процес роботи ==
Термінальний клієнт після встановлення зв'язку з термінальним сервером пересилає на останній дані, що вводяться (натискання клавіш, переміщення миші) і, можливо, надає доступ до локальних ресурсів (наприклад, принтер, дискові ресурси, пристрій читання смарт-карт, локальні порти (COM / LPT) ). Термінальний сервер надає середовище для роботи (термінальна сесія), в якій виконуються програми користувача. Результат роботи сервера передається на клієнта, як правило, це зображення монітора і звук (при його наявності).
Переваги термінального сервера
*Зниження тимчасових витрат на адміністрування
*Підвищення безпеки - зниження ризику інсайдерських зломів
*Зниження витрат на програмне й апаратне забезпечення
*Зниження витрати електроенергії
Недоліки
*Концентрація всієї функціональності в рамках одного (декількох) серверів - вихід з ладу будь-якого елементу між додатком і клієнтами (сервер, комутатори, СКС) призводить до простою багатьох користувачів.
*Посилюються негативні наслідки помилок конфігурації і роботи ПО (наслідки помилок позначаються не на окремих користувачів, а на всіх користувачів сервера відразу ж)
*Проблеми з ліцензуванням (деяке ПЗ не передбачає ситуації роботи декількох користувачів на одному комп'ютері або вимагає використання дорогих версій).

== Проблеми ліцензування ==
В умовах використання вільного ПЗ (такого, як X Window System) проблема ліцензування не виникає. Для ПЗ, що передбачає в ліцензійній угоді обмеження на кількість копій / користувачів, виникають труднощі.
В умовах термінального сервера можуть використовуватися такі моделі ліцензування:
*Per seat (per device - на робоче місце) - для кожного пристрою (тонкого клієнта чи робочої станції) потрібна окрема ліцензія, незалежно від кількості користувачів. Подібна схема використовується при ліцензуванні Terminal Services у складі Windows Server.
*Per user (на користувача) - для кожного користувача (незалежно від кількості одночасно працюючих користувачів) потрібна окрема ліцензія.
*Per connection (конкурентна ліцензія) - для кожного з'єднання потрібна окрема ліцензія, при цьому кількість користувачів / робочих місць не грає ролі - важлива кількість одночасно обслуговуваних користувачів. Таку систему ліцензування використовує Citrix Metaframe. У цьому випадку існує пул ліцензій, кожне нове з'єднання забирає одну ліцензію з пулу. Ліцензія повертається в пул при закінченні з'єднання.
У багатьох великих пакетах ПО передбачається особливий сервіс - сервер ліцензій (додаток, що займається обліком, видачею і прийомом ліцензій). В умовах великих мереж рекомендується виділення під сервер ліцензій окремого комп'ютера (або кількох - для резервування).
== Види термінальних серверів ==
*[[Microsoft Windows Terminal Server]] (поставляється в Microsoft Windows Server)
*[[Citrix Metaframe]]
*[[X Window System]]
*[[NX NoMachine]]
*[[FreeNX]]
*[[RX @ Etersoft]]
*[[LinuxWizard GET]]

Термінальний сервер

2011-05-12T00:34:29Z

Natal ka: Створена сторінка: '''Термінальний сервер''', ''сервер терміналів'' (англ. ''terminal server'') - сервер, що надає клієнтам…

'''Термінальний сервер''', ''сервер терміналів'' (англ. ''terminal server'') - сервер, що надає клієнтам обчислювальні ресурси (процесорний час, пам'ять, дисковий простір) для вирішення завдань. Технічно, '''термінальний сервер''' являє собою дуже потужний комп'ютер (або кластер), з'єднаний по мережі з термінальними клієнтами - які, як правило, являють собою малопотужні або застарілі робочі станції або спеціалізовані рішення для доступу до термінального сервера. Термінальний сервер служить для віддаленого обслуговування користувача з наданням робочого столу.

== Процес роботи ==
Термінальний клієнт після встановлення зв'язку з термінальним сервером пересилає на останній дані, що вводяться (натискання клавіш, переміщення миші) і, можливо, надає доступ до локальних ресурсів (наприклад, принтер, дискові ресурси, пристрій читання смарт-карт, локальні порти (COM / LPT) ). Термінальний сервер надає середовище для роботи (термінальна сесія), в якій виконуються програми користувача. Результат роботи сервера передається на клієнта, як правило, це зображення монітора і звук (при його наявності).
Переваги термінального сервера
*Зниження тимчасових витрат на адміністрування
*Підвищення безпеки - зниження ризику інсайдерських зломів
*Зниження витрат на програмне й апаратне забезпечення
*Зниження витрати електроенергії
Недоліки
*Концентрація всієї функціональності в рамках одного (декількох) серверів - вихід з ладу будь-якого елементу між додатком і клієнтами (сервер, комутатори, СКС) призводить до простою багатьох користувачів.
*Посилюються негативні наслідки помилок конфігурації і роботи ПО (наслідки помилок позначаються не на окремих користувачів, а на всіх користувачів сервера відразу ж)
*Проблеми з ліцензуванням (деяке ПЗ не передбачає ситуації роботи декількох користувачів на одному комп'ютері або вимагає використання дорогих версій).

== Проблеми ліцензування ==
В умовах використання вільного ПЗ (такого, як X Window System) проблема ліцензування не виникає. Для ПЗ, що передбачає в ліцензійній угоді обмеження на кількість копій / користувачів, виникають труднощі.
В умовах термінального сервера можуть використовуватися такі моделі ліцензування:
*Per seat (per device - на робоче місце) - для кожного пристрою (тонкого клієнта чи робочої станції) потрібна окрема ліцензія, незалежно від кількості користувачів. Подібна схема використовується при ліцензуванні Terminal Services у складі Windows Server.
*Per user (на користувача) - для кожного користувача (незалежно від кількості одночасно працюючих користувачів) потрібна окрема ліцензія.
*Per connection (конкурентна ліцензія) - для кожного з'єднання потрібна окрема ліцензія, при цьому кількість користувачів / робочих місць не грає ролі - важлива кількість одночасно обслуговуваних користувачів. Таку систему ліцензування використовує Citrix Metaframe. У цьому випадку існує пул ліцензій, кожне нове з'єднання забирає одну ліцензію з пулу. Ліцензія повертається в пул при закінченні з'єднання.
У багатьох великих пакетах ПО передбачається особливий сервіс - сервер ліцензій (додаток, що займається обліком, видачею і прийомом ліцензій). В умовах великих мереж рекомендується виділення під сервер ліцензій окремого комп'ютера (або кількох - для резервування).
== Види термінальних серверів ==
[[Microsoft Windows Terminal Server]] (поставляється в Microsoft Windows Server)
[[Citrix Metaframe]]
[[X Window System]]
[[NX NoMachine]]
[[FreeNX]]
[[RX @ Etersoft]]
[[LinuxWizard GET]]

Алгоритм Хаффмана

2011-05-12T00:23:20Z

Natal ka: Створена сторінка: '''Алгоритм Хаффмана''' - адаптивний жадібний алгоритм оптимального префіксного кодування…

'''Алгоритм Хаффмана''' - адаптивний жадібний алгоритм оптимального префіксного кодування алфавіту з мінімальною надмірністю. Був розроблений в 1952 році аспірантом Массачусетського технологічного інституту Девідом Хаффманом при написанні ним курсової роботи. В даний час використовується в багатьох програмах стиснення даних.
На відміну від алгоритму Шеннона - Фано, алгоритм Хаффмана залишається завжди оптимальним і для вторинних алфавітів з більш ніж двома символами.
Цей метод кодування складається з двох основних етапів:
*Побудова оптимального кодового дерева.
*Побудова відображення код-символ на основі побудованого дерева.

== Кодування Хаффмана ==
Один з перших алгоритмів ефективного кодування інформації був запропонований Д. А. Хаффманом в 1952 році. Ідея алгоритму полягає в наступному: знаючи ймовірності входження символів в повідомленні, можна описати процедуру побудови кодів змінної довжини, що складаються з цілого кількості бітів. Символам з більшою ймовірністю присвоюються більш короткі коди. Коди Хаффмана володіють властивістю префіксності, що дозволяє однозначно їх декодувати.
Класичний алгоритм Хаффмана на вході отримує таблицю частот входженн символів у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Хаффмана (Н-дерево).
*Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, який може дорівнювати або ймовірності, або кількості входжень символу в стиснутому повідомленні.
*Вибираються два вільних вузла дерева з найменшими вагами.
*Створюється їх батько з вагою, рівною їх сумарній вазі.
*Батько додається в список вільних вузлів, а двоє його дітей (нащадків) видаляються з цього списку.
*Одній дузі, котра виходить з батька, ставиться у відповідність біт 1, іншій - біт 0.
*Кроки, починаючи з другого, повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і буде вважатися коренем дерева.
Припустимо, у нас є наступна таблиця частот:

{|border=1

|-
| 15 || 7 || 6 || 6 || 5
|-
| А || Б || В || Г || Д
|}

Цей процес можна представити як побудова дерева, коріння якого - символ з сумою ймовірностей об'єднаних символів, що вийшов при об'єднанні символів з останнього кроку, його n0 нащадків - символи з попереднього кроку і т. д.
Щоб визначити код для кожного із символів, що входять до повідомлення, ми повинні пройти шлях від листа дерева, відповідного цьому символу, до кореня дерева, накопичуючи біти при переміщенні по гілках дерева. Отримана таким чином послідовність бітів є кодом даного символу, записаним у зворотному порядку.
Для даної таблиці символів коди Хаффмана будуть виглядати наступним чином.
{|border=1
|-
| А || Б || В || Г || Д
|-
| 0 || 100 || 101 || 110 || 111
|}

Оскільки жоден з отриманих кодів не є префіксом іншого, вони можуть бути однозначно декодовані при читанні їх з потоку. Крім того, найбільш частий символ повідомлення А закодований найменшою кількістю біт, а найбільш рідкісний символ Д - найбільшим.
При цьому загальна довжина повідомлення, що складається з наведених у таблиці символів, складе 87 біт (у середньому 2,2308 біта на символ). При використанні рівномірного кодування загальна довжина повідомлення склала б 117 біт (рівно 3 біта на символ). Зауважимо, що [[ентропія]] джерела, незалежним чином породжує символи з зазначеними частотами складає ~ 2,1858 біта на символ, тобто надмірність побудованого для такого джерела коду Хаффмана, що розуміється, як різниця середнього числа біт на символ від ентропії, становить менше 0,05 біт на символ.
Класичний алгоритм Хаффмана має ряд істотних недоліків. По-перше, для відновлення вмісту стиснутого повідомлення декодер повинен знати таблицю частот, якою користувався кодер. Отже, довжина стиснутого повідомлення збільшується на довжину таблиці частот, яка повинна надсилатися попереду даних, що може звести нанівець всі зусилля зі стиснення повідомлення. Крім того, необхідність наявності повної частотної статистики перед початком власне кодування вимагає двох проходів за повідомленням: одного для побудови моделі повідомлення (таблиці частот і Н-дерева), другий для себе власне кодування. По-друге, надмірність кодування звертається в нуль лише в тих випадках, коли ймовірності кодованих символів є зворотними ступенями числа 2. По-третє, для джерела з ентропією, що не перевищує 1 (наприклад, для двійкового джерела), безпосереднє застосування коду Хаффмана безглуздо.

== Адаптивне стиснення ==
Адаптивне стиснення дозволяє не передавати модель повідомлення разом з ним самим і обмежитися одним проходом за повідомленням як при кодуванні, так і при декодуванні.
У створенні алгоритму адаптивного кодування Хаффмана найбільші складнощі виникають при розробці процедури ОбновітьМодельСімволом (); можна було б просто вставити всередину цієї процедури повне побудова дерева кодування Хаффмана. У результаті ми отримали б самий повільний у світі алгоритм стиснення, тому що побудова Н-дерева - це занадто велика робота і проводити її при обробці кожного символу нерозумно. На щастя, існує спосіб модифікувати вже існуюче Н-дерево так, щоб відобразити обробку нового символу.
Оновлення дерева при зчитуванні чергового символу повідомлення складається з двох операцій.
Перша - збільшення ваги вузлів дерева. Спочатку збільшуємо вагу листа, відповідного вважалося символом, на одиницю. Потім збільшуємо вагу батька, щоб привести його у відповідність з новими значеннями ваги у дітей. Цей процес продовжується до тих пір, поки ми не доберемося до коріння дерева. Середнє число операцій збільшення ваги одно середній кількості бітів, необхідних для того, щоб закодувати символ.
Друга операція - перестановка вузлів дерева - потрібно тоді, коли збільшення ваги вузла призводить до порушення властивості впорядкованості, тобто тоді, коли збільшена вага вузла став більше, ніж вага наступного по порядку вузла. Якщо і далі продовжувати обробляти збільшення ваги, рухаючись до кореня дерева, то наше дерево перестане бути деревом Хаффмана.
Щоб зберегти впорядкованість дерева кодування, алгоритм працює наступним чином. Нехай новий збільшена вага вузла дорівнює W +1. Тоді починаємо рухатися за списком у бік збільшення ваги, поки не знайдемо останній вузол з вагою W. Переставимо поточний і знайдений вузли між собою в списку, відновлюючи таким чином порядок в дереві. (При цьому батьки кожного з вузлів теж зміняться.) На цьому операція перестановки закінчується.
Після перестановки операція збільшення ваги вузлів продовжується далі. Наступний вузол, вага якого буде збільшений алгоритмом, - це новий батько вузла, збільшення ваги якого викликало перестановку.

== Переповнення ==
У процесі роботи алгоритму стиснення вага вузлів у дереві кодування Хаффмана неухильно зростає. Перша проблема виникає тоді, коли вага кореня дерева починає перевершувати місткість осередку, в якому він зберігається. Як правило, це 16-бітове значення і, отже, не може бути більше, ніж 65535. Друга проблема, яка заслуговує ще більшої уваги, може виникнути значно раніше, коли розмір найдовшого коду Хаффмана перевершує місткість осередку, який використовується для того, щоб передати його у вихідний потік. Декодеру все одно, якої довжини код він декодує, оскільки він рухається зверху вниз по дереву кодування, вибираючи з вхідного потоку по одному біту. Кодер же повинен починати від аркуша дерева і рухатися вгору до кореня, збираючи біти, які потрібно передати. Зазвичай це відбувається зі змінною типу «ціле», і, коли довжина коду Хаффмана перевершує розмір типу «ціле» в бітах, настає переповнення.
Можна довести, що максимальну довжину код Хаффмана для повідомлень з одним і тим же вхідним алфавітом буде мати, якщо частоти символів утворює послідовність Фібоначчі. Повідомлення з частотами символів, рівними числах Фібоначчі до Fib (18), - це відмінний спосіб протестувати роботу програми стиснення по Хаффману.

== Масштабування ваг вузлів дерева Хаффмана ==
Беручи до уваги сказане вище, алгоритм оновлення дерева Хаффмана повинен бути змінений таким чином: при збільшенні ваги потрібно перевіряти його на досягнення допустимого максимуму. Якщо ми досягли максимуму, то необхідно «масштабувати» вагу, зазвичай розділивши вага листя на ціле число, наприклад, 2, а потім перерахувавши вага всіх інших вузлів.
Однак при розподілі ваги навпіл виникає проблема, пов'язана з тим, що після виконання цієї операції дерево може змінити свою форму. Пояснюється це тим, що ми ділимо цілі числа і за розподілі відкидаємо дробову частину.
Правильно організоване дерево Хаффмана після масштабування може мати форму, значно відрізняється від вихідної. Це відбувається тому, що масштабування призводить до втрати точності нашої статистики. Але зі збором нової статистики наслідки цих «помилок» практично сходять нанівець. Масштабування ваги - досить дорога операція, оскільки вона призводить до необхідності заново будувати все дерево кодування. Але, оскільки необхідність у ній виникає відносно рідко, то з цим можна змиритися.
''Виграш від масштабування''
Масштабування ваги вузлів дерева через певні інтервали дає несподіваний результат. Незважаючи на те, що при масштабуванні відбувається втрата точності статистики, тести показують, що воно призводить до кращих показників стиснення, ніж якщо б масштабування відкладалося. Це можна пояснити тим, що поточні символи стисливого потоку більше «схожі» на своїх близьких попередників, ніж на тих, які зустрічалися набагато раніше. Масштабування призводить до зменшення впливу «давніх» символів на статистику і до збільшення впливу на неї «недавніх» символів. Це дуже складно виміряти кількісно, але, в принципі, масштабування робить позитивний вплив на ступінь стиснення інформації. Експерименти з масштабуванням в різних точках процесу стиснення показують, що ступінь стиснення сильно залежить від моменту масштабування ваги, але не існує правила вибору оптимального моменту масштабування для програми, орієнтованої на стиск будь-яких типів інформації.

== Застосування ==
Стиснення даних за Хаффману застосовується при стисканні фото-і відеозображень ([[JPEG]], стандарти стиснення [[MPEG]]), в архіваторах ([[PKZIP]], [[LZH]] та ін), в протоколах передачі даних MNP5 і MNP7.

Комп'ютерний термінал

2011-05-11T23:29:57Z

Natal ka: Створена сторінка: '''Комп'ютерний термінал''' - електронний або електромеханічний пристрій, що використовуєт…

'''Комп'ютерний термінал''' - електронний або електромеханічний пристрій, що використовується для взаємодії користувача з [[комп'ютером]] або комп'ютерною системою. Ранні комп'ютерні термінали були відносно недорогими, але повільними, в порівнянні з введенням з [[перфокарт]] або [[перфострічки]]. Однак, у міру того як технологія поліпшувалася, і особливо з появою відео-дисплеїв, термінали витіснили інші способи введення-виведення. Пов'язаним нововведенням стала система поділу часу ([[англ.]] ''time sharing''), завдяки якій кілька користувачів могли одночасно працювати з однією системою, кожен зі свого термінала.
Термінал - це [[пристрій введення-виведення]], його основні функції полягають у відображенні і введенні даних. Пристрій із значним обсягом обробки даних називають ''smart terminal'' або "[[товстий клієнт]]" ([[англ.]] ''fat client''). Термінал, що сильно залежить від своєї хост-машини, на якій виконуються основні обчислення, називають [[тонким клієнтом]] ([[англ.]] ''thin client'').

== Історія ==
Перші термінали, що підключалися до комп'ютерів, були електромеханічні «теле-принтери» ([[англ.]] ''teleprinter, TTY''), вже використовувалися в телеграфії. Пізніше були розроблені друкуючі термінали, такі як DECwriter. Але швидкість взаємодії з машиною була обмежена невисокою швидкістю друку, та друкована копія для процесу безпосереднього спілкування не була необхідною.

== Текстові термінали ==
'''Текстовий термінал''' (або частіше просто '''термінал''', іноді також '''текстова консоль''') - це інтерфейс комп'ютера для послідовної передачі даних - введення і зображення тексту. Інформація представляється у вигляді масиву зумовлених знаків.
Спочатку, текстові термінали були електронними пристроями, що підключаються до послідовного порту, але пізніше в комп'ютери стали вбудовувати текстову консоль. У [[графічному інтерфейсі]] користувача використовуються програми - [[емулятори терміналу]].
У [[POSIX]]-сумісних системах, таких як [[UNIX]] і [[Linux]], робота користувача з терміналом здійснюється за допомогою особливої підсистеми, званої [[TTY-абстракцією]].

== Див. також ==
[[Термінальний сервер]]