• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

Thuật toán thám mã Affine

Đây là nơi để các bạn trao đổi về cấu trúc dữ liệu và giải thuật

Điều hành viên: Điều hành

Hình đại diện của người dùng
vuathongtin
Điều hành viên
Điều hành viên
Bài viết: 1028
Ngày tham gia: CN 02/05/2010 10:03 pm
Đến từ: Xứ sở DG
Has thanked: 2 time
Been thanked: 105 time
Liên hệ:

Thuật toán thám mã Affine

Gửi bàigửi bởi vuathongtin » T.Sáu 18/02/2011 5:18 pm

Mình đang làm bài tập liên quan đến thám mã Affine, a e nào biết thuật toán thám mã Affine thì chia sẻ mình với,


Bùi Thành Nhân
CNTT-Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Skype:vuathongtin

Hình đại diện của người dùng
lungocqua
Guru
Guru
Bài viết: 1225
Ngày tham gia: T.Ba 18/08/2009 11:51 am
Đến từ: Phú Hữu - Nhơn Trạch - Đồng Nai
Been thanked: 5 time
Liên hệ:

Re: Thuật toán thám mã Affine

Gửi bàigửi bởi lungocqua » T.Sáu 18/02/2011 8:44 pm

Ta đã trở lại và quên hết tất cả! :D

Hình đại diện của người dùng
vuathongtin
Điều hành viên
Điều hành viên
Bài viết: 1028
Ngày tham gia: CN 02/05/2010 10:03 pm
Đến từ: Xứ sở DG
Has thanked: 2 time
Been thanked: 105 time
Liên hệ:

Re: Thuật toán thám mã Affine

Gửi bàigửi bởi vuathongtin » T.Sáu 18/02/2011 9:46 pm

Thank Sang ! nhưng ko phải cái mình cần, cái Sang đưa là mã hóa và giải mã, thám mã nói theo tích cực dò, tìm mã, nói theo tiêu cực là phá, hack mã.
Bùi Thành Nhân
CNTT-Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Skype:vuathongtin

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Re: Thuật toán thám mã Affine

Gửi bàigửi bởi vo_minhdat2007 » T.Sáu 18/02/2011 10:06 pm

À, vụ phá mã thì hồi trước lúc học bồi dưỡng HSG có làm rồi :D Thử 1 bài thế này xem (đề rút gọn thôi): Cho 1 đoạn text đã mã hoá (theo kiểu mã hoá Ceasar, chuyển từ kí tự này sang kí tự khác), đồng thời có 1 file "từ điển", tức chứa các từ có nghĩa để mò cách giải mã. Hãy tìm cách giải mã dựa vào file từ điển ấy.

Hình đại diện của người dùng
vuathongtin
Điều hành viên
Điều hành viên
Bài viết: 1028
Ngày tham gia: CN 02/05/2010 10:03 pm
Đến từ: Xứ sở DG
Has thanked: 2 time
Been thanked: 105 time
Liên hệ:

Re: Thuật toán thám mã Affine

Gửi bàigửi bởi vuathongtin » T.Bảy 19/02/2011 9:41 am

Cái của Đạt cũng nằm trong hệ mã hóa cổ điển,
Bùi Thành Nhân
CNTT-Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Skype:vuathongtin

Hình đại diện của người dùng
vuathongtin
Điều hành viên
Điều hành viên
Bài viết: 1028
Ngày tham gia: CN 02/05/2010 10:03 pm
Đến từ: Xứ sở DG
Has thanked: 2 time
Been thanked: 105 time
Liên hệ:

Re: Thuật toán thám mã Affine

Gửi bàigửi bởi vuathongtin » T.Bảy 26/02/2011 11:03 am

1. Mã Hóa AFFINE

Mã hóa

Hình ảnh

Với x là vị trí của kí tự trong bảng chữ cái : A ... Z (tương ứng với 0... 25)
, UCLN(a,26)=1

  1.  byte mahoaaffine(char kitu,int a, int b)
  2.         {
  3.             return (byte)((a * ((byte)kitu)-65 + b) % 26);
  4.         }


Test như sau : Chuỗi "WAR" mã hóa với khóa (a=7,b=10) sẽ được : "IKZ"

================================================================

Giải mã :
Hình ảnh

Với a^-1 được tính bằng :
Hình ảnh
Tức là phải dùng đến Euclid Mở Rộng :

Tham khảo tại đây :
http://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid_m%E1%BB%9F_r%E1%BB%99ng

  1.     int euclid_morong(int a, int m)
  2.         {
  3.             int x, y, z, r, q, bandau = m;
  4.             x = 0; y = 1; z = 0;
  5.  
  6.             while (a > 0)
  7.             {
  8.                 r = m % a;
  9.                 if (r != 0)
  10.                 {
  11.                     q = m / a;
  12.                     z = x - (y * q);
  13.                     m = a;
  14.                     a = r;
  15.                     x = y;
  16.                     y = z;
  17.                 }
  18.                 else break;
  19.             }
  20.             return (z > 0 ? z : bandau + z);
  21.         }


Code giải mã sẽ là :
  1.      byte giaimaaffine(char kitu, int a, int b)
  2.         {
  3.             return (byte)((euclid_morong (a,26)*((byte)kitu-65-b+208))%26);
  4.         }



Chú thích : mình dùng ASCII để tính vị trí kí tự trong bản mã (a...z). Còn 1 cách nữa là đưa vào mảng.

Phá mã :

Cách 1 : dùng vét cạn
Ý tưởng : Dùng 2 vòng lặp để liệt kê các khóa; Hàm giải mã để lấy đc kết quả của 2 khóa tương ứng

  1.  public void vetcan_affine(string chuoi)
  2.         {
  3.             int[] bangmakhoaa = {1,3,5,7,9,11,15,17,19,21,23,25};
  4.  
  5.             for (int i = 0; i < bangmakhoaa.Length; i++)
  6.             {
  7.                 for (int j = 0; j < 26; j++)
  8.                 {
  9.                             string chuoimahoa = "";
  10.                             for (int kt = 0; kt < chuoi.Length; kt++)
  11.                             {
  12.                                 chuoimahoa += ((char)(giaimaaffine(char.Parse(chuoi.Substring(kt, 1).ToUpper()), bangmakhoaa[i], j) + 65)).ToString() + " ";
  13.                             }
  14.                     }
  15.                 }
  16.             }

phane.jpg


Cách 2 : Dựa vào tần suất xuất hiện kí tự của bản mã
Ý tưởng :
+ Tính tần suất
+ Từ tần suất --> Lập hệ phương trình đồng dư 2 ẩn
==> Tính được khóa a,b tương ứng
Bùi Thành Nhân
CNTT-Sở Thông tin & Truyền thông tỉnh Phú Yên
giasulaptrinh.com
Skype:vuathongtin

phuongphamdng
Bài viết: 1
Ngày tham gia: T.Năm 14/03/2013 10:20 am

Re: Thuật toán thám mã Affine

Gửi bàigửi bởi phuongphamdng » T.Năm 14/03/2013 10:27 am

ths vuathongtin nhiều nhá. Có thể cho xin demo được không bạn (phuongphamdng@gmail.com)


Quay về “Cấu trúc dữ liệu và giải thuật”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách