Добавлена реализация схемы Эль-Гамаля по заданию

4 files changed, 428 insertions, 38 deletions

diff --git a/sem2/src/algo.rs b/sem2/src/algo.rs
index 0a54c72..60d0bad 100644
--- a/sem2/src/algo.rs
+++ b/sem2/src/algo.rs
@@ -1,6 +1,10 @@
 use crate::mpn::Number;
 
 pub fn rabin_miller_test(n: &Number, k: u32) -> bool {
+    if n < &4.into() {
+        todo!("реализация Рабина-Миллера для n < 4");
+    }
+
     if n.clone() % 2.into() == 0.into() {
         return false;
     }
diff --git a/sem2/src/elgamal.rs b/sem2/src/elgamal.rs
new file mode 100644
index 0000000..c53622e
--- /dev/null
+++ b/sem2/src/elgamal.rs
@@ -0,0 +1,218 @@
+use crate::algo;
+use crate::mpn::Number;
+use std::collections::HashMap;
+
+#[derive(Debug)]
+pub struct OpenKey {
+    pub y: Number,
+    pub g: Number,
+    pub p: Number,
+}
+
+#[derive(Debug)]
+pub struct SecretKey {
+    pub x: Number,
+}
+
+fn factorization(x: &Number) -> Vec<Number> {
+    let mut factors = Vec::new();
+    let mut n = x.clone();
+    let mut i: Number = 2.into();
+    let mut flag = true;
+    while i.clone() * i.clone() <= n.clone() && flag {
+        if n.clone() % i.clone() == 0.into() {
+            factors.push(i.clone());
+            while n.clone() % i.clone() == 0.into() {
+                n = n.clone() / i.clone();
+                if algo::rabin_miller_test(&n, 10) {
+                    flag = false;
+                    break;
+                }
+            }
+        }
+        i = i.clone() + 1.into();
+    }
+    if n.clone() > 1.into() {
+        factors.push(n.clone());
+    }
+    return factors;
+}
+
+pub fn is_primitive_root(x: &Number, p: &Number, powers: &Vec<Number>) -> bool {
+    if !algo::rabin_miller_test(p, 10) {
+        todo!("примитивный корень для составных чисел");
+    }
+    for l in powers {
+        if x.pow_mod(&l, p).unwrap() == 1.into() {
+            return false;
+        }
+    }
+    return true;
+}
+
+pub fn generate_keypair(p: &Number) -> (OpenKey, SecretKey) {
+    let p1 = p.clone() - 1.into();
+    let powers = factorization(&p1);
+    let mut g;
+    loop {
+        g = p.random_below();
+        if gcd(&g, &p1) == 1.into() {
+            continue;
+        }
+        if g.pow_mod(&(p1.clone() / 2.into()), p).unwrap() != 1.into() {
+            continue;
+        }
+        if is_primitive_root(&g, &p, &powers) {
+            break;
+        }
+    }
+
+    let x = g.random_below();
+    let y = g.pow_mod(&x, &p).unwrap();
+
+    println!("Найден примитивный корень: {g}");
+    println!("x = {x}");
+    println!("y = {y}");
+
+    return (OpenKey { y, g, p: p.clone() }, SecretKey { x });
+}
+
+pub const ALPHABET: &str =
+    "абвгдеёжзиклмнопрстуфхцчшщъыьэюя1234567890!\"'$%#,.;:{}[]<>*\n\t";
+
+fn get_encoding() -> HashMap<char, String> {
+    let mut map = HashMap::new();
+    let mut enc = 111;
+    for ch in ALPHABET.chars() {
+        let mut txt = enc.to_string();
+        while txt.contains('0') {
+            enc += 1;
+            txt = enc.to_string();
+        }
+        map.insert(ch, txt);
+        enc += 1;
+    }
+    return map;
+}
+
+fn get_inv_encoding() -> HashMap<String, char> {
+    let encoding = get_encoding();
+    let mut inv = HashMap::new();
+    for (k, v) in &encoding {
+        inv.insert(v.clone(), k.clone());
+    }
+    return inv;
+}
+
+fn gcd(a: &Number, b: &Number) -> Number {
+    if *b == 0.into() {
+        return a.clone();
+    } else {
+        return gcd(&b.clone(), &(a.clone() % b.clone()));
+    }
+}
+
+fn session_key(p: &Number) -> Number {
+    let p1 = p.clone() - 1.into();
+    loop {
+        let k = p1.random_below();
+        if gcd(&k, &p1) == 1.into() {
+            return k;
+        }
+    }
+}
+
+pub fn filter_text(text: &String) -> String {
+    let mut chars = String::new();
+    for ch in text.to_lowercase().chars() {
+        if ALPHABET.contains(ch) {
+            chars.push(ch);
+        }
+    }
+    return chars;
+}
+
+pub fn encrypt_text(text: &String, open: OpenKey) -> Vec<(Number, Number)> {
+    let encoding = get_encoding();
+    println!("Кодировка: {encoding:?}");
+    let mut ciphertext = String::new();
+    for ch in text.chars() {
+        ciphertext.extend(encoding[&ch].chars());
+    }
+
+    println!("Перекодированный текст: {ciphertext}");
+
+    let mut result = Vec::new();
+    let ciphertext = ciphertext.chars().collect::<Vec<char>>();
+    let mut i = 0;
+    loop {
+        let mut num = String::new();
+        while i < ciphertext.len()
+            && (num.len() == 0 || Number::parse(&num, 10).unwrap() < open.p)
+        {
+            num.push(ciphertext[i]);
+            i += 1;
+        }
+        let num2;
+        if i == ciphertext.len() {
+            let nn = Number::parse(&num, 10).unwrap();
+            if nn >= open.p {
+                i -= 1;
+                num2 = Number::parse(&num[..num.len() - 1], 10).unwrap();
+            } else {
+                num2 = nn.clone();
+            }
+        } else {
+            i -= 1;
+            num2 = Number::parse(&num[..num.len() - 1], 10).unwrap();
+        }
+        let num = num2;
+        println!("Блок: {num}");
+        let k = session_key(&open.p);
+        let a = open.g.pow_mod(&k, &open.p).unwrap();
+        let b = (open.y.pow_mod(&k, &open.p).unwrap() * num.clone())
+            % open.p.clone();
+        result.push((a, b));
+        if i == ciphertext.len() {
+            break;
+        }
+    }
+    return result;
+}
+
+pub fn decrypt_text(cipher: &String, key: SecretKey, open: OpenKey) -> String {
+    let mut encoded = String::new();
+    for elem in cipher.split(":") {
+        let ab = elem.split(",").collect::<Vec<&str>>();
+        let a = Number::parse(ab[0], 10).unwrap();
+        let b = Number::parse(ab[1], 10).unwrap();
+
+        println!("Считанные a и b: {a} {b}");
+        let pow = open.p.clone() - 1.into() - key.x.clone();
+        let m =
+            (b.clone() * a.pow_mod(&pow, &open.p).unwrap()) % open.p.clone();
+        println!("Расшифровка: {m}");
+
+        encoded.extend(format!("{m}").chars());
+    }
+
+    println!("Закодированный текст: {encoded}");
+    let inv_enc = get_inv_encoding();
+    println!("Обратная кодировка: {inv_enc:?}");
+    let encoded = encoded.chars().into_iter().collect::<Vec<char>>();
+    let mut result = String::new();
+    let mut i = 0;
+    loop {
+        let mut num = String::new();
+        while i < encoded.len() && !inv_enc.contains_key(&num) {
+            num.push(encoded[i]);
+            i += 1;
+        }
+        result.push(inv_enc[&num]);
+        if i == encoded.len() {
+            break;
+        }
+    }
+
+    return result;
+}
diff --git a/sem2/src/main.rs b/sem2/src/main.rs
index adf47b8..7c458f6 100644
--- a/sem2/src/main.rs
+++ b/sem2/src/main.rs
@@ -1,54 +1,221 @@
-use fastrand;
-use inquire::Text;
-use std::time::Instant;
+use inquire::{Select, Text};
+use std::fs::{self, File};
+use std::io::{self, Write};
+use std::path::{Path, PathBuf};
+
+use crate::elgamal::{decrypt_text, encrypt_text, OpenKey, SecretKey};
+use crate::mpn::Number;
 mod algo;
+mod elgamal;
 mod mpn;
 mod program;
 
-fn main() {
-    let radix = 10;
-
-    let q_text = match Text::new("Введите число q:").prompt() {
-        Ok(text) => text,
-        Err(_) => return,
-    };
-    let q = match mpn::Number::parse(&q_text, radix as u8) {
-        Ok(number) => number,
-        Err(what) => {
-            println!("{what}");
-            return;
+fn files_recursive(dir: &Path) -> io::Result<Vec<PathBuf>> {
+    let mut dir_front = Vec::new();
+    let mut files = Vec::new();
+    dir_front.push(dir.to_owned());
+    while dir_front.len() != 0 {
+        let dir = dir_front.pop().unwrap();
+        for entry in fs::read_dir(dir)? {
+            let path = entry?.path();
+            if path.is_dir() {
+                dir_front.push(path.clone());
+            } else {
+                files.push(path.clone());
+            }
         }
-    };
-
-    if !algo::rabin_miller_test(&q, 10) {
-        println!("Число q должно быть простым");
-        return;
     }
+    return Ok(files);
+}
 
-    let mut p;
-    loop {
-        let s = mpn::Number::random_num(fastrand::usize(1..=30), radix);
-        println!("s = {s}");
-        p = q.clone() * s + 1.into();
-        if algo::rabin_miller_test(&p, 10) {
-            break;
+fn dirs_recursive(dir: &Path) -> io::Result<Vec<PathBuf>> {
+    let mut dir_front = Vec::new();
+    let mut dirs = Vec::new();
+    dir_front.push(dir.to_owned());
+    dirs.push(dir.to_owned());
+    while dir_front.len() != 0 {
+        let dir = dir_front.pop().unwrap();
+        for entry in fs::read_dir(dir)? {
+            let path = entry?.path();
+            if path.is_dir() {
+                dir_front.push(path.clone());
+                dirs.push(path.clone());
+            }
         }
     }
-    println!("Сгенерированное простое p: {p}");
+    return Ok(dirs);
+}
 
-    let t_start = Instant::now();
-    let g = program::find_of_order(&p, &q);
-    let t_elapsed = t_start.elapsed();
+fn write_keys(
+    open: OpenKey,
+    open_path: String,
+    secret: SecretKey,
+    secret_path: String,
+) {
+    let mut open_file = File::create(open_path).unwrap();
+    let key = format!("{} {} {}", open.y, open.g, open.p);
+    open_file.write_all(key.as_bytes()).unwrap();
 
-    match g {
-        Ok(res) => {
-            println!("Найденный элемент g: {res}");
-        }
-        Err(msg) => {
-            println!("{msg}");
+    let mut secret_file = File::create(secret_path).unwrap();
+    let key = format!("{}", secret.x);
+    secret_file.write_all(key.as_bytes()).unwrap();
+}
+
+fn read_open_key(path: String) -> OpenKey {
+    let open_text = fs::read_to_string(path).unwrap();
+    let numbers = open_text.split(" ").collect::<Vec<&str>>();
+    let y = Number::parse(numbers[0], 10).unwrap();
+    let g = Number::parse(numbers[1], 10).unwrap();
+    let p = Number::parse(numbers[2], 10).unwrap();
+    return OpenKey { y, g, p };
+}
+
+fn read_secret_key(path: String) -> SecretKey {
+    let secret_text = fs::read_to_string(path).unwrap();
+    let x = Number::parse(&secret_text, 10).unwrap();
+    return SecretKey { x };
+}
+
+fn main() {
+    let operation = Select::new(
+        "Выберите тип операции:",
+        vec!["Генерация ключей", "Зашифрование", "Расшифрование"],
+    )
+    .prompt()
+    .unwrap();
+
+    if operation == "Генерация ключей" {
+        let dir_entries = dirs_recursive(Path::new("."))
+            .unwrap()
+            .into_iter()
+            .map(|e| e.to_str().unwrap().to_owned())
+            .collect::<Vec<String>>();
+        let result_path =
+            Select::new("Выберите куда сохранить результат:", dir_entries)
+                .prompt()
+                .unwrap();
+        let open_name = Text::new("Имя для файла с открытым ключом:")
+            .prompt()
+            .unwrap();
+        let secret_name = Text::new("Имя для файла с закрытым ключом:")
+            .prompt()
+            .unwrap();
+        let p_text = Text::new("Введите простое p:").prompt().unwrap();
+        let p = Number::parse(&p_text, 10).unwrap();
+        if !algo::rabin_miller_test(&p, 10) {
+            println!("Число p должно быть простым");
             return;
         }
+        let (op, cl) = elgamal::generate_keypair(&p);
+        let open_path = Path::new(&result_path)
+            .join(&open_name)
+            .to_string_lossy()
+            .to_string();
+        let secret_path = Path::new(&result_path)
+            .join(&secret_name)
+            .to_string_lossy()
+            .to_string();
+        write_keys(op, open_path, cl, secret_path);
     }
 
-    println!("Операция выполнена за {} наносекунд", t_elapsed.as_nanos());
+    if operation == "Зашифрование" {
+        let entries = files_recursive(Path::new("."))
+            .unwrap()
+            .into_iter()
+            .map(|e| e.to_str().unwrap().to_owned())
+            .collect::<Vec<String>>();
+        let open_name =
+            Select::new("Выберите файл с открытым ключом:", entries.clone())
+                .prompt()
+                .unwrap();
+        let plain_file =
+            Select::new("Выберите файл для зашифрования:", entries)
+                .prompt()
+                .unwrap();
+
+        let dir_entries = dirs_recursive(Path::new("."))
+            .unwrap()
+            .into_iter()
+            .map(|e| e.to_str().unwrap().to_owned())
+            .collect::<Vec<String>>();
+        let result_path =
+            Select::new("Выберите куда сохранить результат:", dir_entries)
+                .prompt()
+                .unwrap();
+
+        let cipher_name =
+            Text::new("Введите название для файла с шифротекстом:")
+                .prompt()
+                .unwrap();
+
+        let open_key = read_open_key(open_name);
+        let plaintext = fs::read_to_string(plain_file).unwrap();
+        println!("{plaintext}");
+        println!("Отфильтрованный текст:");
+        let plaintext = elgamal::filter_text(&plaintext);
+        println!("{plaintext}");
+        let cipher = encrypt_text(&plaintext, open_key);
+
+        let mut elements = Vec::new();
+        for (a, b) in &cipher {
+            let elem = format!("{},{}", a, b);
+            elements.push(elem);
+        }
+        let ciphertext = elements.join(":");
+        println!("Полученный шифротекст: {ciphertext}");
+        let cipher_path = Path::new(&result_path)
+            .join(&cipher_name)
+            .to_string_lossy()
+            .to_string();
+        fs::write(cipher_path, ciphertext.as_bytes())
+            .expect("Не получилось записать шифротекст");
+    }
+
+    if operation == "Расшифрование" {
+        let entries = files_recursive(Path::new("."))
+            .unwrap()
+            .into_iter()
+            .map(|e| e.to_str().unwrap().to_owned())
+            .collect::<Vec<String>>();
+        let secret_name =
+            Select::new("Выберите файл с закрытым ключом:", entries.clone())
+                .prompt()
+                .unwrap();
+        let open_name =
+            Select::new("Выберите файл с открытым ключом:", entries.clone())
+                .prompt()
+                .unwrap();
+        let cipher_file =
+            Select::new("Выберите файл для расшифрования:", entries)
+                .prompt()
+                .unwrap();
+
+        let dir_entries = dirs_recursive(Path::new("."))
+            .unwrap()
+            .into_iter()
+            .map(|e| e.to_str().unwrap().to_owned())
+            .collect::<Vec<String>>();
+        let result_path =
+            Select::new("Выберите куда сохранить результат:", dir_entries)
+                .prompt()
+                .unwrap();
+        let plain_name =
+            Text::new("Введите название для файла с расшифровкой:")
+                .prompt()
+                .unwrap();
+
+        let open = read_open_key(open_name);
+        let secret = read_secret_key(secret_name);
+        let ciphertext = fs::read_to_string(cipher_file).unwrap();
+        let plaintext = decrypt_text(&ciphertext, secret, open);
+        println!("Расшифрованный текст:");
+        println!("{plaintext}");
+
+        let plain_path = Path::new(&result_path)
+            .join(&plain_name)
+            .to_string_lossy()
+            .to_string();
+        fs::write(plain_path, plaintext.as_bytes())
+            .expect("Не получилось записать расшифровку");
+    }
 }
diff --git a/sem2/src/program.rs b/sem2/src/program.rs
index 3a8dd26..016a63e 100644
--- a/sem2/src/program.rs
+++ b/sem2/src/program.rs
@@ -1,6 +1,7 @@
 use crate::algo;
 use crate::mpn::Number;
 
+#[allow(dead_code)]
 pub fn find_of_order(p: &Number, q: &Number) -> Result<Number, String> {
     if !algo::rabin_miller_test(&p, 10) {
         return Err("Число p должно быть простым".to_string());