🟠 Հակեր 🤖

Համուզված եմ, որ գրեթե բոլորդ բազմիցս լսել եք, տարբեր հակերային հարձակումների մասին, որոնց արդյունքում պետությունները, կազմակերպությունները կամ անգամ անհատները կրում են մեծ դրամական, ռեպուտացիոն կամ այլ վնասներ։ Իսկ երբևէ մտածել եք, թե ինչպե՞ս են տեղի ունենում այդպիսի հարձակումները։
Նախորդ խնդրում մենք նշեցինք, որ Կեսարի կոդավորումը այդքան էլ հուսալի եղանակ չէ տվյալները գաղտնագրելու համար։ Դա նշանակում է, որ ունենալով միայն գաղտնագրված տվյալը, հնարավոր է վերականգնել օրիգինալ տեքստը առանց բանալու արժեքը իմանալու։ Հակերային հարձակումների թիրախ շատ հաճախ հանդիսանում են հենց ոչ հուսալի գաղտնագրման ալգորթիմները։ Իմանալով ալգորիթմի թերությունները, հակերները կարողանում են վերկանգնել տվյալները, առանց գաղտնագրման բանալին իմանալու։
Կարող ե՞ք ինքուրույն փորձել ապակոդավորել Կեսարի կոդավորմամբ գաղտնագրված այս տողը՝ ”Gsrkvexypexmsr csy lezi gvegoih xli irgvctxih qiwweki!"։ Մտածե՛ք, թե ինչպե՞ս է ընդհանրապես հնարավոր առանց բանալու արժեքը իմանալու վերականգնել սկզբնական տվյալը։ Եթե դժվարանում եք, օգտվե՛ք հուշումից։

Հուշում

💡
Կեսարի գաղտնագրման ժամանակ բանալին կարող է լինել ցանկացած թիվ, սակայն միևնույն է գոյություն ունի գաղտնագրման ընդհամենը 25 տարբերակ։ 25-ը այդքան էլ մեծ թիվ չէ, մենք կարող ենք վերականգնել սկզբնական տողը, հերթով փորձելով բանալու արժեքները 1-ից միչև 25։ Եթե հերթական բանալու կիրառման արդյունքում ստանում ենք կարդացվող անգլերեն բառեր, ուրմեն կարողացել ենք վերականգնել սկզբնական տողը։
Հուսով եմ կարողացաք վերականգնել սկզբնական տողը։ Ալգորիթմի այս տեսակը, երբ դիտարկվում են մուտքային արժեքների բոլոր հնարավոր տարբերակները, կոչվում է հատարկաման մեթոդ (անգլերենով` brute force, ռուսերենով՝ полный перебор)։ Հատարկման եղանակը շատ հաճախ օգտագործվում է հակերային հարձակումների ժամանակ, գաղտնաբառերի, գաղտնագրված տվյալների վերակագնման համար։
 
Դե ինչ, ժամանակն է, որ մենք ևս մեզ փորձենք հակերի 🤖 դերում և փորձենք գրել ծրագիր, որը ավտոմատ կվերականգնի Կեսարի կոդով գաղտնագրված տվյալները։
Բանալու արժեքը գուշակելու համար մենք ոչ թե կօգտվենք հատարկման եղանակից, այլ կդիտարկենք ևս մեկ ալգորիթմ, որը հիմնված է վիճակագրության վրա։ Հիշում ե՞ք Բառաղախ խնդիրը, որտեղ անգլերեն այբուբենի ամեն տառին տրվում է միավոր։ Ընդ որում, վիճակագրորեն, ինչքան հաճախ է հանդիպում տառը, այնքան քիչ միավոր է նրան հատկացվում։ Ըստ վիճակագրության, անգլերեն լեզվում ամենահաճախ օգտագործվող տառը E տառն է (12.702% միջինում)։ Երկրորդ ամենատարածվածը T տառն է (9.056%), այնուհետև A տառը (8.17%) և այդպես շարունակ։
Ունենալով այս վիճակագրական տվյալները, կարող ենք գուշակել գաղտնագրման բանալու արժեքը հետևյալ կերպ՝
  • Գաղտնագրված տեքստում ամենաշատ հանդիպող տառը մեծ հավանականությամբ համապատասխանում է օրիգինալ տեքստի E տառին (կամ e տառին)։
  • Երկրորդ ամենաշատ հանդիպող տառը մեծ հավանականությամբ համապտասխանում է օրիգինալ տեքստի T (t) տառին։
  • Երրորդը ամենշատ հանդիպող տառը A (a) տառին։
  • Օրինակ, եթե գաղտնագրված տեքստում ամենաշատ հանդիպող տառը H -ն է, ապա հավանականությունը մեծ է, որ գաղտնագրման բանալու արժեքը հավասար կլինի (‘H’ - ‘E’) % 26 = 3։ Կարևոր է հասկանալ, որ սա ընդհամենը հավանական արժեքն է։ Եթե երկրորդ ամենաշատ հանդիպող տառը Q-ն է, իսկ երրորդը՝ X-ը, ապա հավանականությունը էլ ավելի մեծ է, որ բանալու արժեքը հավասար կլինի 3 (քանի որ Q, T և X, A տառերը նույնպես գտնվում են իրարից 3 հեռավորության վրա)։
 
Այսպիսով, եթե ամենահաճախ հանդիպող 3 տառերի համար բանալու արժեքը նույն է, ապա շատ մեծ հավանականությամբ մենք գտել ենք գաղտնագրման բանալու իրական արժեքը և կարող ենք փորձել վերականգնել օրիգինալ տեքստը։

Դե ինչ, եկե՛ք նախագծենք և իրականացնենք ծրագիր, որը մուտքում ստանում է գաղտնագրված տողը, գուշակում և էկրանին տպում է բանալու արժեքը և վերականգնված տողը։

  1. Եթե ամենահաճախ հանդիպող 3 տառերի համար բանալու արժեքը նույն է, էկրանին պետք է տպել բանալու արժեքը և ապակոդավորած տողը հետևյալ կերպ՝
    1. “Key value is possibly: “ այնուհետև բանալու արժեքը։
    2. “Decrypted text: “ այնուհետև ապակոդավորված տողը։
  1. Եթե ամենահաճախ հանդիպող 3 տառերի համար բանալու արժեքը տարբերվում է, էկրանին տպել “Impossible to detect key from the given text” տողը։
#include <iostream>
#include <string>

int main() {
    std::string text;
    std::cout << "Crypted Text: ";
    std::getline(std::cin, text);
    std::cout << text << std::endl;
    // Put your code here
}
 

Հուշում 1

Խնդիրը կարելի է բաժանել երկու մասի՝
  1. Հաշվել ամեն սիմվոլի հանդիպելու քանակը և գտնել 3 ամենհաճախ հանդիպող սիմվոլները։
  1. Վերականգնել նախնական տեքստը։

🚩Հուշում 2

Ամեն տառի հանդիպելու քանակը կարող եք հաշվել հետևյալ կերպ՝
  1. Հայտարարել int charactersCount[26] զանգված, որտեղ 26 - ը անգլերեն այբուբենի տառերի քանակն է։ Այս զանգվածում կպահենք ամեն տառի հանդիպելու քանակը։ Օրինակ` charactersCount[0]-ն իրենից կներկայացնի a տառի հանդիպելու քանակը, charactersCount[1]-ը՝ b տառի հանդիպելու քանակը և այդպես շարունակ։
  1. Մուտքային տեքստի ամեն տառի համար charactersCount զանգվածի համապատասխան էլեմենտի արժեքը մեծացնել 1-ով։

🚩 Հուշում 2.1

for (int i = 0; i < text.size(); ++i) {
       if(isalpha(text[i])) {
           char upper = toupper(text[i]);
           charactersCount[upper - 'A']++;
       }
   }

Ծրագրավորման ոճ

Խնդիրը գրելուց առաջ, ևս մեկ անգամ կարդացեք “Ծրագրավորման ոճ” դասը։ Մի գրե՛ք ամբողջ ծրագիրը մեկ main ֆունկցիայի մեջ։ Մտածեք, թե ի՞նչ տրամաբանական հատվածների (ֆունկցիաների) է կարելի բաժանել ծրագիրը, որպեսզի կոդը լինի հնարավորինս ընթեռնելի։ Ֆունկցիաներ գրելիս, փորձեք պահպանել «եզակի պատասխանատվության» (single responsobility) սկզբունքը։ Օգտագործե՛ք մտածված և իմաստային անուններ և՛ փոփոխականների և՛ ֆունկցիաների համար։

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue