Автор: Пользователь скрыл имя, 20 Мая 2013 в 01:01, курсовая работа
Криптоанализ традиционно используется для решения таких задач, как восстановление исходной информации по ее криптограмме, вычисление закрытого ключа по известному открытому, формирование электронной цифровой подписи сообщения без знания закрытого ключа, а также создание фальшивого электронного документа, соответствующего известной подписи.
В данной работе рассмотрим алгоритмы шифрования и дешифрования системы RSA и проведём её криптоанализ.
Введение 3
1 Техническое задание 5
2 Алгоритм шифрования RSA 6
2.1 Описание RSA 6
2.2 Нахождение простых чисел 6
2.3 Нахождение взаимно простых чисел 7
2.4 Решение уравнения Диофанта 8
2.5 Большие числа и работа с ними 8
2.5.1 Хранение больших чисел, алгебраическое сложение, умножение 9
2.5.2 Алгоритм быстрого возведения в степень 9
2.5.3 BigInteger 10
3 Средства взлома 11
3.1 Алгоритм взлома основанный на факторинге 12
4 Руководство пользователя 13
Выводы 16
Список использованной литературы 17
Приложение А (листинг основных модулей) 18
Приложение Б (диск с программой и документацией) 31
</Grid.ColumnDefinitions>
<TextBox Name="text_box_find_p" MaxWidth="400" TextWrapping="Wrap" Text="0"/>
<Button Name="button_find_p" Content="Новое" Grid.Column="1" Click="FindPButton_Click"/>
</Grid>
<TextBlock Text="Простое число q:" Visibility="Collapsed"/>
<Grid Visibility="Collapsed">
<Grid.ColumnDefinitions>
<ColumnDefinition/>
<ColumnDefinition/>
</Grid.ColumnDefinitions>
<TextBox Name="text_box_find_q" MaxWidth="400" TextWrapping="Wrap" Text="0"/>
<Button Name="button_find_q" Content="Новое" Grid.Column="1" Click="FindQButton_Click"/>
</Grid>
<Button Name="btton_find_keys" Content="Получить ключи" Click="FindKeysButton_Click"/>
<TextBlock Text="Общая часть ключа:"/>
<TextBox Name="text_box_find_n" IsReadOnly="True" MaxWidth="400" TextWrapping="Wrap"/>
<TextBlock Text="Открытая часть ключа:"/>
<TextBox Name="text_box_find_e" IsReadOnly="True" MaxWidth="400" TextWrapping="Wrap"/>
<TextBlock Text="Секретная часть ключа:"/>
<TextBox Name="text_box_find_d" IsReadOnly="True" MaxWidth="400" TextWrapping="Wrap"/>
</StackPanel>
<StackPanel Name="stack_panel_crack" Grid.Column="2" Grid.Row="1" Grid.RowSpan="2" Visibility="Collapsed">
<TextBlock Text="Общая часть ключа:"/>
<TextBox Name="text_box_crack_n" TextWrapping="Wrap" MaxWidth="400"/>
<TextBlock Text="Открытая часть ключа:"/>
<TextBox Name="text_box_crack_e" TextWrapping="Wrap" MaxWidth="400"/>
<Button Name="button_crack_keys" Content="Взломать
ключ:" Click="CrackKeysButton_Click"/
<TextBlock Text="Секретная часть ключа:"/>
<TextBox Name="text_box_crack_d" TextWrapping="Wrap" MaxWidth="400" IsReadOnly="True"/>
</StackPanel>
</Grid>
</Window>
Код логики программы:
using System.Windows;
using System.Numerics;
namespace CodingWPF
{
/// <summary>
/// Логика взаимодействия для MainWindow.xaml
/// </summary>
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
}
private void ClearWindow()
{
text_block_n.Visibility = System.Windows.Visibility.
text_box_n.Visibility = System.Windows.Visibility.
text_block_e.Visibility = System.Windows.Visibility.
text_box_e.Visibility = System.Windows.Visibility.
text_block_d.Visibility = System.Windows.Visibility.
text_box_d.Visibility = System.Windows.Visibility.
button_coding.Visibility = System.Windows.Visibility.
button_decoding.Visibility = System.Windows.Visibility.
//stack_panel_find_keys.
//stack_panel_crack.Visibility = System.Windows.Visibility.
}
private void New_Click(object sender, RoutedEventArgs e)
{
text_box_code.Text="";
ClearWindow();
}
private void Open_Click(object sender, RoutedEventArgs e)
{
Microsoft.Win32.OpenFileDialog ofd = new Microsoft.Win32.
if (ofd.ShowDialog(this)==true)
{
System.IO.StreamReader sr = new System.IO.StreamReader(ofd.
text_box_code.Text = sr.ReadToEnd();
sr.Close();
}
}
private void Save_Click(object sender, RoutedEventArgs e)
{
Microsoft.Win32.SaveFileDialog sfd = new Microsoft.Win32.
if (sfd.ShowDialog(this) == true)
{
System.IO.StreamWriter sw = new System.IO.StreamWriter(sfd.
sw.Write(text_box_code.Text);
sw.Close();
}
}
private void Exit_Click(object sender, RoutedEventArgs e)
{
Close();
}
private void CodingShow_Click(object sender, RoutedEventArgs e)
{
ClearWindow();
text_block_n.Visibility = System.Windows.Visibility.
text_box_n.Visibility = System.Windows.Visibility.
text_block_e.Visibility = System.Windows.Visibility.
text_box_e.Visibility = System.Windows.Visibility.
button_coding.Visibility = System.Windows.Visibility.
}
private void DecodingShow_Click(object sender, RoutedEventArgs e)
{
ClearWindow();
text_block_n.Visibility = System.Windows.Visibility.
text_box_n.Visibility = System.Windows.Visibility.
text_block_d.Visibility = System.Windows.Visibility.
text_box_d.Visibility = System.Windows.Visibility.
button_decoding.Visibility = System.Windows.Visibility.
}
private void Coding_Click(object sender, RoutedEventArgs e)
{
ClearWindow();
BigInteger N = BigInteger.Parse(text_box_n.
BigInteger E = BigInteger.Parse(text_box_e.
RSA rsa = new RSA(N);
rsa.E = E;
text_box_code.Text=rsa.Coding(
}
private void Decoding_Click(object sender, RoutedEventArgs e)
{
ClearWindow();
BigInteger N = BigInteger.Parse(text_box_n.
BigInteger D = BigInteger.Parse(text_box_d.
RSA rsa = new RSA(N);
rsa.D = D;
text_box_code.Text = rsa.Coding(text_box_code.Text, false);
}
private void FindKeys_Click(object sender, RoutedEventArgs e)
{
if (stack_panel_find_keys.
stack_panel_find_keys.
else
stack_panel_find_keys.
}
private void CrackKeys_Click(object sender, RoutedEventArgs e)
{
if (stack_panel_crack.Visibility == System.Windows.Visibility.
stack_panel_crack.Visibility = System.Windows.Visibility.
else
stack_panel_crack.Visibility = System.Windows.Visibility.
}
private void FindPButton_Click(object sender, RoutedEventArgs e)
{
}
private void FindQButton_Click(object sender, RoutedEventArgs e)
{
}
private void FindKeysButton_Click(object sender, RoutedEventArgs e)
{
RSA rsa = new RSA();
rsa.CalculateKeys(BigInteger.
text_box_find_n.Text = rsa.N.ToString();
text_box_find_e.Text = rsa.E.ToString();
text_box_find_d.Text = rsa.D.ToString();
}
private void CrackKeysButton_Click(object sender, RoutedEventArgs e)
{
RSA rsa = new RSA(BigInteger.Parse(text_box_
rsa.CrackKeys();
text_box_crack_d.Text = rsa.D.ToString();
}
}
}
Код основного класса:
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
namespace CodingWPF
{
class RSA
{
private BigInteger n;
/// <summary>
/// Общая часть ключа.
/// </summary>
public BigInteger N
{
get
{
return n;
}
set
{
n = value;
}
}
private BigInteger e;
/// <summary>
/// Открытая часть ключа.
/// </summary>
public BigInteger E
{
get
{
return e;
}
set
{
e = value;
}
}
private BigInteger d;
/// <summary>
/// Секретная часть ключа.
/// </summary>
public BigInteger D
{
get
{
return d;
}
set
{
d = value;
}
}
/// <summary>
/// Конструктор.
/// </summary>
public RSA()
{
}
/// <summary>
/// Конструктор.
/// </summary>
/// <param name="n">Общая часть ключа.</param>
public RSA(BigInteger n)
{
this.n = n;
}
/// <summary>
/// Конструктор.
/// </summary>
/// <param name="n">Общая часть ключа.</param>
/// <param name="e">Открытая часть ключа.</param>
public RSA(BigInteger n, BigInteger e)
{
this.n = n;
this.e = e;
}
/// <summary>
/// Конструктор.
/// </summary>
/// <param name="n">Общая часть ключа.</param>
/// <param name="e">Открытая часть ключа.</param>
/// <param name="d">Секретная часть ключа.</param>
public RSA(BigInteger n, BigInteger e, BigInteger d)
{
this.n = n;
this.e = e;
this.d = d;
}
private byte[] StringToBytes(string s, int n)
{
int count = 2 * s.Length / n;
if ((2 * s.Length) % n != 0)
count++;
byte[] res = new byte[count * n];
for (int i = 0; i < s.Length; i++)
{
int r = Convert.ToUInt16(s[i]);
res[2 * i] = (byte)r;
res[2 * i + 1] = (byte)(r >> 8);
}
return res;
}
private string BytesToString(byte[] b)
{
System.Text.StringBuilder sb = new System.Text.StringBuilder(b.
for (int i = 0; i < b.Length / 2; i++)
{
int r = b[2 * i + 1];
r <<= 8;
r += b[2 * i];
sb.Append(Convert.ToChar(r));
}
if (b.Length % 2 != 0)
{
int r = b[b.Length-1];
sb.Append(Convert.ToChar(r));
}
while ((int)sb[sb.Length - 1] == 0)
sb.Remove(sb.Length - 1, 1);
return sb.ToString();
}
public string Coding(string s, bool is_coding)
{
int inp_block_length;
int out_block_length;
BigInteger c;
if (is_coding)
{
inp_block_length = N.ToByteArray().Length - 1;
out_block_length = N.ToByteArray().Length;
c = E;
}
else
{
inp_block_length = N.ToByteArray().Length;
out_block_length = N.ToByteArray().Length - 1;
c = D;
}
byte[] inp_block = new byte[inp_block_length];
byte[] inp_blockes = StringToBytes(s, inp_block_length);
int count = inp_blockes.Length / inp_block_length;
byte[] out_block = new byte[out_block_length];
byte[] out_blockes = new byte[count * out_block_length];
for (int i = 0; i < count; i++)
{
System.Array.Copy(inp_blockes, i * inp_block_length, inp_block, 0, inp_block_length);
BigInteger tbi = new BigInteger(inp_block);
tbi = BigInteger.ModPow(tbi, c, N);
out_block = tbi.ToByteArray();
int t;
if (out_block.Length < out_block_length)
t = out_block.Length;
else
t = out_block_length;
for (int j = 0; j < t; j++)
out_blockes[i * out_block_length + j] = out_block[j];
}
return BytesToString(out_blockes);
}
private List<UInt32> simples = new List<UInt32>();
/// <summary>
/// Заполнение списка простых чисел.
/// </summary>
/// <param name="max">Верхний диапазон простых чисел.</param>
private void FillSimples(UInt32 inp_max)
{
UInt16 max = (UInt16)inp_max;
simples.Clear();
bool[] A = new bool[max];
for (UInt16 i = 2; i < max; i++)
A[i] = true;
for (UInt16 i = 2; i < max; i++)
{
if (A[i])
for (Int32 j = i * i; j>0 && j < max; j += i)
A[j] = false;
}
for (UInt16 i = 2; i < max; i++)
if (A[i])
simples.Add(i);
if (inp_max!=max)
{
for (UInt32 i = max; i < inp_max; i++)
{
bool r = false;
List<UInt32>.Enumerator enumerator = simples.GetEnumerator();
while (enumerator.MoveNext() && !r)
{
r = enumerator.Current % i == 0;
}
if (!r)
simples.Add(i);
}
}
}
private void Diofant(List<BigInteger> alpha, out BigInteger x, out BigInteger y)
{
BigInteger xx;
BigInteger yy;
x = 0;
y = 1;
for (int i = alpha.Count - 1; i >= 0; i--)
{
xx = y;
yy = x - alpha[i] * y;
x = xx;
y = yy;
}
}
private void Alpha(BigInteger a, BigInteger b, out List<BigInteger> alpha, out bool indicator)
{
indicator = true;
BigInteger c;
BigInteger cc;
alpha = new List<BigInteger>();
BigInteger GCD = b;
c = a % b;
cc = c;
while (c > 0)
{
alpha.Add(a / b);
c = a % b;
a = b;
b = c;
}
alpha.Add(0);
if (cc > 0)
GCD = a;
indicator = GCD == 1;
}
/// <summary>
/// Получение ключей.
/// </summary>
/// <param name="min">Нижний диапазон простых чисел.</param>
/// <param name="max">Верхний диапазон простых чисел.</param>
public void CalculateKeys(BigInteger p, BigInteger q)
{
Random rand = new Random();
FillSimples(UInt16.MaxValue);
p = simples[rand.Next(simples.
q = simples[rand.Next(simples.
n = p * q;
BigInteger fi = (p - 1) * (q - 1);
e = simples[rand.Next(simples.
while (fi % e == 0)