Lý thuyết mật mã | Mọi người vào đây trao đổi crypto nhé ! [Archive] – Cộng đồng C Việt

Lâu lắm rồi pete không có cảm giác vui như mấy hôm nay :D. Không biết tại sao :D. Nhìn lại forum mình cũng đã gần 2 năm rồi mà chưa thấy phát triển mạnh cho lắm. Quanh quẩn cũng chỉ qua box C/C++ cơ bản thôi, mà không thấy nâng cao mấy :D. Ngồi chat với mấy ông bạn pete nghĩ ra cái này. Thời đại mới, xã hội phát triển, lập trình viên mà không đi nhanh theo thời đại thì không thể làm việc được. Chắc là đúng :D?. Vì thế forum cần mọi người cùng tham khảo và trao đổi nhiều hơn, cùng nhau tiến bộ. Topic này xin bắt đầu bằng các vấn đề về mật mã hóa CRYPTO. Cái này chắc mọi người biết để làm gì :D.

* Vì đây là bài đầu tiên, mà pete cũng có giới hạn về vấn đề này nên mình đưa ra thuật toán mã hóa đầu tiên rất đơn giản 😀

[Method : chuyển chuỗi sang ASCII Numbers sau đó viết ngược lại, lấy cặp 2 chữ số lại convert từ số sang char theo bảng ASCII, được cái code đã mã hóa. Chuỗi nhập vào giới hạn : chữ cái thường, chữ hoa, và số.]

Ví dụ : chuoiIn = “ABC” -> chuoiInRaSo = “656667” -> chuoiOutSo=”766656″ -> chuoiOut = “LB8”;

* Anh em cùng luyện skill cho ra sản phẩm mã hóa và giải mã nhé ^^, sản phẩm viết = gì cũng OK, C/C++/C# Console hay API đều hay cả ^^.

* Ai có thuật toán crypt gì hay ý kiến gì thì cũng cho anh em biết ý kiến tham khảo nhé !

===Có gì không phải anh em góp ý để cải thiện nhé===
———Tất cả vì lợi ích chung————–

Bạn đang đọc: Lý thuyết mật mã | Mọi người vào đây trao đổi crypto nhé ! [Archive] – Cộng đồng C Việt

ntnam

Các bác xem thử:

http://teamdn.info/crypto/index.php

php nó support nhiều hàm quá đâm ra cũng mất hay, mong được xem các bài bằng C của anh em 🙂

kidkid

chuoiIn = “ABC” -> chuoiInRaSo = “656667” -> chuoiOutSo=”766656″ -> chuoiOut = “LB8”;

uhm cách trên của pete thì cũng hay nhưng mà phải có thêm 1 số điều kiện ràng buộc nữa, nếu chuổi nhập vào có chữ có mã ASCII là 89 thì ngược lại sẽ là 98 nếu in ra thì không thể ở dạng kí tự được.

kidkid nghĩ như thế này : Chúng ta có thể lấy 1 kí tự nào đó làm khóa ví dụ đơn giản như trong mật thư : kidkid cho chuỗi ” anh yeu em ” và có khóa là a = b như vậy chuỗi xuất ra sẽ là : “boi jfv fn” như thế là đơn giản. Nếu phức tạp thì rườm ra hơn một chút. như vậy sẽ ok ngay !

kidkidẶc lâu rồi mới vào lại mà chẳng thấy ma nào cho quan điểm thế này ? Lão pete lập ra thì phải xung phong đi đầu chứ chẳng lẽ đợi đồng đội nhắc à ? Kid tui chờ lâu quá nên đành spam vậy !
neverland87

Hi, việc mà pete giao tớ đã hoàn thành, 1 chương trình mô tả thuật toán mà pete đã nói, do chương trình này được làm trong quá trình mình mày mó Windows Forms nên không được pro lắm, post lên để mọi người test xem có bug nào không? Có gì phản hồi….cho pete. Sau đây là link tải file thực thi chương trình (lưu ý: do được làm từ C# nên yêu cầu máy các bạn phải cài .NET FRAMEWORK v2.0)
http://i158.photobucket.com/albums/t111/minhdanh87/hinh.png

http://www.zshare.net/download/crypto-exe-kf2.html
http://www.zshare.net/download/crypto-exe-kyz.html

soda_chanhmuoi

#include
#include
#include
#include
#include
int daoSo(int s)
{
int t,m;
int x=s;
t=x%10;
while(x/10>0)
{
x=x/10;
m=x%10;
t=t*10 +m;
}
return t;
}
void main()
{
char s1[1000],s2[1000];
int t1[1000],len,t2[1000];
cout<<"Nhap vao chuoi can ma hoa:";
cin>>s1;
len=strlen(s1);
cout<<"Ma ASCII:";
for(int i=0;i {
t1[i]=s1[i];
cout< cout< cout<<"Dao ma ASCII:";
for(i=len-1;i>=0;i–)
{
t2[i]=daoSo(t1[i]);
s2[i]=t2[i];
cout< }
cout< cout<<"Cac ki tu sau khi ma hoa:";
for(i=len-1;i>=0;i–)
cout< cout< getch();
}
Vừa làm xong kiểm tra dùm! chỉ là consol thôi!

Xcross87

Ok !
Hiện giờ :

ID | Points
————————
ntnam 5/10
neverland87 6/10 <---như trên---1 extra do diễn dịch quá trình crypt :D>
soda_chanhmuoi 5/10

Lần sau post lên nhớ có thêm source và cipher của các cậu nhé ^^! Để mọi người tham gia thảo luận và nghiên cứu.

phanvankhai

Source code của neverland87 : 😀

http://www.mediafire.com/?9az2dtoezt2

soda_chanhmuoi

Ok !
Hiện giờ :
Code:

ID | Points
————————
ntnam 5/10
neverland87 6/10 <---như trên---1 extra do diễn dịch quá trình crypt :D>
soda_chanhmuoi 5/10

Lần sau post lên nhớ có thêm source và cipher của các cậu nhé ^^! Để mọi người tham gia thảo luận và nghiên cứu.
cipher là j` vậy?”soda_chanhmuoi 5/10 ” là sao?

Xcross87

Một số thuật ngữ Crypto :

+ Encrypt : mã hóa
+ Decrypt : giải mã
+ Cipher : phương pháp mã hóa (=algorithm)
+ Key : Một chuỗi kí tự chữ số từ thuật toán mà có thể dùng để mã hóa và giải mã.
+ Plaintext : dữ liệu chưa được mã hóa hoặc đã được giải mã
+ Ciphertext : dữ liệu được mã hóa

Trên là 1 số thuật ngữ cơ bản trong Crypto.
Tại sao mình làm cái Topic về crypto này ?
– Câu trả lời đơn giản : rèn luyện tư duy thuật toán, thực hành kĩ năng lập trình, biết càng nhiều càng ít.
_ Các bạn có thể tham gia thảo luận hoặc không.

=================================================
Một ví dụ về mã hóa :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
————————————————–
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

như vậy nếu như dữ liệu cần mã hóa là :
————————————————–
ATTACK AT DAWN AT THE NORTHERN BRIDGE
————————————————–
trở thành
————————————————–
SLLSUC SL VSOF SL LZW FGJLZWJF TJAVYW
————————————————–

+ Tại sao lại thế ?
+ %Trả lời : để ý thấy các kí tự bị dịch sang phải 18 đơn vị bắt đầu từ A. Vì vậy người ta quy ước Key ( = khóa) = 18. Và đây là một trong những cipher nổi tiếng nhất thể giới, “Caesar Cipher” ( =Mã Xê-da).

$-=Mục tiêu của chúng ta lần này là gì ?
#Bắt đầu bằng các chương trình thể hiện phương pháp mã hóa trên.
#Nhớ post một poster về chương trình mẫu của bạn và source lên cho mọi người tham khảo nhé !

#Học rồi mới biết mình ngu. Vì ngu mới càng phải học cho bằng bạn bằng bè#

@Hết bài 1. <=Cipher Key 18=>

soda_chanhmuoihè, bài mình làm chỉ là để thỏa mãn nhu cầu nhu yếu đề bài, chưa chú ý quan tâm đến thuật toán lắm. Pete post lên 1 bài làm mẫu nhá !
Xcross87

Đây là bài mẫu :

+ Mã hóa key-18 Caesar
+ Mã hóa key-X với 1 + Viết trên C#

http://i177.photobucket.com/albums/w233/pete87_photo/cipher_key_18.jpg

Download Source (http://www.freewebtown.com/lttram/programming/Cipher_Key_18.rar)
Download Program (http://www.freewebtown.com/lttram/programming/Cipher_Key_18.exe)

kidkidChà lão pete giỏi quá ! Kiểu này bạn bè tất cả chúng ta phải thật cố gắng nỗ lực mới được ?
Xcross87

Hix…..giỏi quái gì đâu.
Vẫn kém lắm. Chưa biết gì đâu. Vẫn đang cố gắng cho = anh = em.
Lão Khải với Danh ghê C# lắm. Tranh thủ nã pháo hỏi C# tí 😀

Xcross87

_Chắc hẳn anh em đã biết về phương pháp này. Vì nó có lịch sử lâu đời và nổi tiếng.

Khóa dùng theo cột, tức là sẽ chia plain-text thành mảng 2 chiều trong đó số cột chính là key. Cipher-text thu được bằng cách lấy các cột từ trên xuống dưới cho đến khi hết. Vì vậy phương pháp này làm việc tương đương với các thao tác
trên ma trận .

Ví dụ : Với key = 5 tức là sẽ phải chia thành 5 cột ; giả sử
plaintext = “Pete writes the code”
thì chia thành

1 2 3 4 5
———————
P e t e w
r i t e s
t h e c o
d e
———————

vậy nếu lấy hết từng cột và gom hết thông tin lại ta có
ciphertext = “prtdeihetteeecwso”

http://i177.photobucket.com/albums/w233/pete87_photo/Tran_Cipher_5.jpg

Download Program (http://www.freewebtown.com/lttram/programming/Tran_Cipher_5.exe)

^^’….Sao không ai tham gia nhỉ ??

Xcross87

Đây là code giải thuật cho bài Tranpositions Cipher X ( X : số lượng cột chia )

#include
#include

char *encrypt(char *inTxt, int col)
{
char tmp[255], *outTxt;
int index=0, k=0, next,cnt=0;

while(inTxt[index] != 0)
{
if(isalnum(inTxt[index]))
tmp[k++] = inTxt[index];
index++;
}

tmp[k] = 0 ; // chuỗi thì nhát cuối phải NULL
outTxt = (char*)malloc(k+1);
for(index = 0 ; index < col ; index++)
{
next = 0;
while ( next + index < k )
{
outTxt[cnt++] = tmp[next + index];
next += col;
}
}
outTxt[k] = 0;
return outTxt;
}

int main(void)
{
char inTxt[255], *cipher;
int col;

printf(” Input plain-txt : “); gets(inTxt);
printf(” Number of columns : “); scanf(“%d”,&col);
cipher = encrypt(inTxt,col);
printf(” Cipher-txt : %s”, cipher);
getch();
return 0;
}

Chúc vui vẻ ^^’ !

phanvankhai

http://cdcv-ftp.xm.com/Crypto.PNG

Tôi có chương trình mã hóa với thuật toán tùy chọn này (:-)w !

Lưu ý : Cái này tôi chỉ viết cái Program còn cái file DLL là lấy của người ta nên … (:-)?? 😀

Dowload dính kèm nhé (:-)h

Xcross87

#Càng nhiều càng hay, anh em sưu tập về cùng nhau nghiên cứu ^^’

#Dù biết là người ta viết rồi nhưng vấn đề là mình có làm được không ^^’?

#Biết vậy tại sao không thử ? Thành quả do chính mình làm ra vẫn vui hơn là đi xài thành quả người khác đúng không ?

#Đóng góp và học tập, cùng nhau trao đổi ^^’

#Bác Khải dump ra lấy cái thuật toán nó viết xem :D…Sau này tổng hợp bộ Cryptor tổng hợp do Cviet_2.0 viết nhỉ ^^’?

kidkid

Mã hóa chẳng qua là cách thức ẩn đi khi làm một điều gì đó ?
kidkid ví dụ cái pete đưa ra:

ciphertext = “prtdeihetteeecwso”

Chẳng qua là một trờ chơi mật thư hàng cột thôi. Ở trò chơi mật thư VN chúng ta có rất nhiều cách mã hóa rất đặc biệt tại sao không áp dụng mà phải đi cóp nhặt những thuật toán khác chứ. Chúng ta có thể nghiên cứu nhưng đầu tiên hãy bắt đầu từ chính đất nước chúng ta thì tuyệt vời hơn nhỉ ?

Hôm nào kidkid sẽ post lần lượt các cách mã hóa của VN lên để anh em tham khảo. Hôm nay nhân tiện đọc bài “Mã hóa Hàng Cột” của pete phía trên kidkid đưa thêm cách này có tên mà “mưa dông”anh em đọc thử ?

với cột =5 thì từ pete write code sẽ được chia như sau :

P e t e w
r i t e s
t h e c o
d e

Với cách chia như vậy thì ta sẽ có những chữ sau khi mã hóa là d te rh# pie# etc# teo es. Đậm bản chất việt chứ nhỉ ? nhưng như thế dở quá. Mấy đứa cấp 2 là nó chơi sành hết rồi. Anh em nghiên cứu cách khác cho nó hay hơn. kidkid không viết code được tại chạy trong dos viết làm gì thêm buồn .

Xcross87

#Thế mà forum nhiều bài hỏi về mảng và ma trận lắm đó ^^’

#Biết là một chuyện, học và thực hành là một chuyện ^^!
#Chủ đề này mới bắt đầu thôi, dần dần sẽ đến những cái phức tạp hơn. Chứ bây giờ tương luôn mâys cái chuẩn mã hóa SA, MD Hash, LC thì ma nào biết T_T.
#Với lại làm cái này nhiều viết key_gen cho soft mới dễ và thạo tay nghề ^^!

nguyentuan2

#Với lại làm cái này nhiều viết ****** cho soft mới dễ và thạo tay nghề ^^!

****** là cái j` vậy, khó hiểu quá

kidkidchắc lão ghi gì đó rồi bị biến dạng … tí vào bảo lão sửa thử ?
neverland87

Thấy topic vui quá, vào hỏi chơi, nói như kidkid thiệt là hay, thông thường người ta dùng mấy cái mã hóa này làm máy cái ứng dụng mã hóa văn bản trong việc trao-nhận email. Khổ cái, người Việt mình dùng tiếng Việt, anh em thử nghĩ cách mã hóa đi (mình gà mờ lắm,vào để nêu ý tưởng thôi).
Ví dụ: ‘ư’ –> nó đâu có nằm trong bảng mã ASCII đâu 😀

Xcross87

#Mèng ui, có Unicode nè sao không xài

#Pete đưa đề ra dùng ASCII vì lí do viết trên Dos không có Unicode á.

#Chứ viết = C# toàn ra Unicode không mà ra ASCII cũng được ^^’

soda_chanhmuoiSao viết chương trình tạo mã mà ko viết giải thuật nhỉ ? Viết một gói có nhiều giải pháp tạo mã và giải thuật để cho người dùng chọn. Diễn đàn quay đi quay lại có mấy lão ah ? Mấy ông toàn pro C # mà tui lại chưa học C #, è ! ko tham gia nữa
kidkidChậc đang cần cái giải thuật đây, những chương trình trên giải thuật thì sử dụng key. chậc khó nhỉ ?
HTS

#Chủ đề này mới bắt đầu thôi, dần dần sẽ đến những cái phức tạp hơn. Chứ bây giờ tương luôn mâys cái chuẩn mã hóa SA, MD Hash, LC thì ma nào biết T_T.
Hơi bị nhầm nhá. Có đầy ma lang thang khắp nơi đấy. Ngay vừa nãy thôi em gặp một người cũng có thể gọi là cao thủ vừa ở đây (nick bí mật).

#Với lại làm cái này nhiều viết key_gen cho soft mới dễ và thạo tay nghề ^^!
Hơi nhầm 1 chút. key_gen gì đi nữa thì quan trọng nhất vẫn là thuật toán. Có thuật toán roài thì nó cũng chỉ là 1 bài tập thông thường mà thôi. Cái quan trọng nhất theo tớ là kỹ năng lập trình 😀

ps: Hê hê hê biết bác peter_87 là ai roài. Hóa ra người nhà cả mà ko nhận ra. Dòm topic này thấy nghi nghi. Điều tra một hồi…..Khà khà khà khà…..

ẶC ặc…..diễn đàn tự động chỉnh tử key_gen(ko có _ ) thành ****** .

nguyen190887

Định viết 1 chương trình giải mã cho mấy pác xem thử, nhưng mà suy đi tính lại thấy giải mã thì cũng chả khác j mã hóa vì thuật toán biết hết rồi -> không còn gì là thú vị nữa.
Sao chúng ta không tổ chức một cuộc thi xem ai là người tìm ra phương pháp mã hóa hay nhất, hữu hiệu nhất nhỉ. Cái này hay đấy. Mấy bác admin làm tiên phong đi 🙂
À, làm sao biết cái tụi “be hacked” mã hóa kiểu gì mà mình decrypt nhỉ. Hay là mò kim đáy hồ, cứ thử hết các phương pháp rùi cũng đúng 1 cái. Khó hỉu quá !!!

hailoc12Em nghe nói trong cuộc chiến tranh quốc tế thứ II ông toán học Anh gì ấy đã sản xuất ra máy giải thuật, hoàn toàn có thể giải được hầu hết những kiểu mã hóa của Đức bấy giờ. Chỉ tiếc sau đó biết nhiều quá nên ông ấy bị chính phủ nước nhà khử. Nhưng không biết nguyên tắc của cái máy ấy thế nào
HTS

suy đi tính lại thấy giải mã thì cũng chả khác j mã hóa vì thuật toán biết hết rồi -> không còn gì là thú vị nữa.

Viết thuật toán giải mã MD5 cho tớ coi nào. Nếu cần thuật toán tớ sẽ đưa cho. Decrypt được nó bạn thích zì tớ cũng cho.(=D)>

Định đính kèm file mà sao toàn báo thất bại nhỉ(:-)?? ?

nguyen190887

Viết thuật toán giải mã MD5 cho tớ coi nào. Nếu cần thuật toán tớ sẽ đưa cho. Decrypt được nó bạn thích zì tớ cũng cho.

Định đính kèm file mà sao toàn báo thất bại nhỉ ?

Bạn đưa thử đi, xem mình viết dc không. Mình chưa biết MD5 là gì cả 🙁

kidkid

Chậc vừa mới nghe NT nói về blowfish và MD5 nè. Đúng là mình cũng không rành lắm về máy vụ này. Đọc sách tiếng anh cũng không có gì là khả quan lắm. Sách tiếng việt thì lục mãi ko ra ? Có lẽ là nhờ anh em thôi .

Các chương trình crypt này thì đơn giản mà, với là chúng ta có key cả nên giải mã thì có gì để nói nữa. Kid có đề bài này anh em góp ý coi thử ha .

Chương trình sẽ sinh một chuỗi ngẫu nhiên gồm 4 kí tự (a->z) ví dụ char A[]= “abcd”. Bây giờ chúng ta sẽ viết hàm tìm các kí tự này. rồi xuất ra màn hình .

Vì phạm vi hẹp nên có thể giải bằng quay lui hoặc 4 vòng for cũng được. nhưng nếu mở rộng hơn thì sao ? Chắc chắn chúng ta không dùng cách đó được rồi. Anh em xem góp ý nha .

HTS

Xem thêm: [Crypto] 03 – Mã Affine

Bạn đưa thử đi, xem mình viết dc không. Mình chưa biết MD5 là gì cả 🙁
Ức chế thật. Ko đính kèm file dc. Coi tạm mã nguồn nhé. C hai cộng :D.

file MD5.h

/**
* \file md5.h
*/
#ifndef _MD5_H
#define _MD5_H

#ifdef __cplusplus
extern “C” {
#endif

/**
* \brief MD5 context structure
*/
typedef struct
{
unsigned long total[2]; /*!< number of bytes processed */
unsigned long state[4]; /*!< intermediate digest state */
unsigned char buffer[64]; /*!< data block being processed */
}
md5_context;

/**
* \brief MD5 context setup
*
* \param ctx MD5 context to be initialized
*/
void md5_starts( md5_context *ctx );

/**
* \brief MD5 process buffer
*
* \param ctx MD5 context
* \param input buffer holding the data
* \param ilen length of the input data
*/
void md5_update( md5_context *ctx, unsigned char *input, int ilen );

/**
* \brief MD5 final digest
*
* \param ctx MD5 context
* \param output MD5 checksum result
*/
void md5_finish( md5_context *ctx, unsigned char output[16] );

/**
* \brief Output = MD5( input buffer )
*
* \param input buffer holding the data
* \param ilen length of the input data
* \param output MD5 checksum result
*/
void md5_csum( unsigned char *input, int ilen,
unsigned char output[16] );

/**
* \brief Output = MD5( file contents )
*
* \param path input file name
* \param output MD5 checksum result
* \return 0 if successful, or 1 if fopen failed
*/
int md5_file( char *path, unsigned char output[16] );

/**
* \brief Output = HMAC-MD5( input buffer, hmac key )
*
* \param key HMAC secret key
* \param keylen length of the HMAC key
* \param input buffer holding the data
* \param ilen length of the input data
* \param output HMAC-MD5 result
*/
void md5_hmac( unsigned char *key, int keylen,
unsigned char *input, int ilen,
unsigned char output[16] );

/**
* \brief Checkup routine
*
* \return 0 if successful, or 1 if the test failed
*/
int md5_self_test( void );

#ifdef __cplusplus
}
#endif

#endif /* md5.h */

còn đây là MD5.c

#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif

#include
#include

#include “md5.h”

/*
* 32-bit integer manipulation macros (little endian)
*/
#ifndef GET_UINT32_LE
#define GET_UINT32_LE(n,b,i) \
{ \
(n) = ( (unsigned long) (b)[(i) ] ) \
| ( (unsigned long) (b)[(i) + 1] << 8 ) \
| ( (unsigned long) (b)[(i) + 2] << 16 ) \
| ( (unsigned long) (b)[(i) + 3] << 24 ); \
}
#endif
#ifndef PUT_UINT32_LE
#define PUT_UINT32_LE(n,b,i) \
{ \
(b)[(i) ] = (unsigned char) ( (n) ); \
(b)[(i) + 1] = (unsigned char) ( (n) >> 8 ); \
(b)[(i) + 2] = (unsigned char) ( (n) >> 16 ); \
(b)[(i) + 3] = (unsigned char) ( (n) >> 24 ); \
}
#endif

/*
* MD5 context setup
*/
void md5_starts( md5_context *ctx )
{
ctx->total[0] = 0;
ctx->total[1] = 0;

ctx->state[0] = 0x67452301;
ctx->state[1] = 0xEFCDAB89;
ctx->state[2] = 0x98BADCFE;
ctx->state[3] = 0x10325476;
}

static void md5_process( md5_context *ctx, unsigned char data[64] )
{
unsigned long X[16], A, B, C, D;

GET_UINT32_LE( X[0], data, 0 );
GET_UINT32_LE( X[1], data, 4 );
GET_UINT32_LE( X[2], data, 8 );
GET_UINT32_LE( X[3], data, 12 );
GET_UINT32_LE( X[4], data, 16 );
GET_UINT32_LE( X[5], data, 20 );
GET_UINT32_LE( X[6], data, 24 );
GET_UINT32_LE( X[7], data, 28 );
GET_UINT32_LE( X[8], data, 32 );
GET_UINT32_LE( X[9], data, 36 );
GET_UINT32_LE( X[10], data, 40 );
GET_UINT32_LE( X[11], data, 44 );
GET_UINT32_LE( X[12], data, 48 );
GET_UINT32_LE( X[13], data, 52 );
GET_UINT32_LE( X[14], data, 56 );
GET_UINT32_LE( X[15], data, 60 );

#define S(x,n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 – n)))

#define P(a,b,c,d,k,s,t) \
{ \
a += F(b,c,d) + X[k] + t; a = S(a,s) + b; \
}

A = ctx->state[0];
B = ctx->state[1];
C = ctx->state[2];
D = ctx->state[3];

#define F(x,y,z) (z ^ (x & (y ^ z)))

P( A, B, C, D, 0, 7, 0xD76AA478 );
P( D, A, B, C, 1, 12, 0xE8C7B756 );
P( C, D, A, B, 2, 17, 0x242070DB );
P( B, C, D, A, 3, 22, 0xC1BDCEEE );
P( A, B, C, D, 4, 7, 0xF57C0FAF );
P( D, A, B, C, 5, 12, 0x4787C62A );
P( C, D, A, B, 6, 17, 0xA8304613 );
P( B, C, D, A, 7, 22, 0xFD469501 );
P( A, B, C, D, 8, 7, 0x698098D8 );
P( D, A, B, C, 9, 12, 0x8B44F7AF );
P( C, D, A, B, 10, 17, 0xFFFF5BB1 );
P( B, C, D, A, 11, 22, 0x895CD7BE );
P( A, B, C, D, 12, 7, 0x6B901122 );
P( D, A, B, C, 13, 12, 0xFD987193 );
P( C, D, A, B, 14, 17, 0xA679438E );
P( B, C, D, A, 15, 22, 0x49B40821 );

#undef F

#define F(x,y,z) (y ^ (z & (x ^ y)))

P( A, B, C, D, 1, 5, 0xF61E2562 );
P( D, A, B, C, 6, 9, 0xC040B340 );
P( C, D, A, B, 11, 14, 0x265E5A51 );
P( B, C, D, A, 0, 20, 0xE9B6C7AA );
P( A, B, C, D, 5, 5, 0xD62F105D );
P( D, A, B, C, 10, 9, 0x02441453 );
P( C, D, A, B, 15, 14, 0xD8A1E681 );
P( B, C, D, A, 4, 20, 0xE7D3FBC8 );
P( A, B, C, D, 9, 5, 0x21E1CDE6 );
P( D, A, B, C, 14, 9, 0xC33707D6 );
P( C, D, A, B, 3, 14, 0xF4D50D87 );
P( B, C, D, A, 8, 20, 0x455A14ED );
P( A, B, C, D, 13, 5, 0xA9E3E905 );
P( D, A, B, C, 2, 9, 0xFCEFA3F8 );
P( C, D, A, B, 7, 14, 0x676F02D9 );
P( B, C, D, A, 12, 20, 0x8D2A4C8A );

#undef F

#define F(x,y,z) (x ^ y ^ z)

P( A, B, C, D, 5, 4, 0xFFFA3942 );
P( D, A, B, C, 8, 11, 0x8771F681 );
P( C, D, A, B, 11, 16, 0x6D9D6122 );
P( B, C, D, A, 14, 23, 0xFDE5380C );
P( A, B, C, D, 1, 4, 0xA4BEEA44 );
P( D, A, B, C, 4, 11, 0x4BDECFA9 );
P( C, D, A, B, 7, 16, 0xF6BB4B60 );
P( B, C, D, A, 10, 23, 0xBEBFBC70 );
P( A, B, C, D, 13, 4, 0x289B7EC6 );
P( D, A, B, C, 0, 11, 0xEAA127FA );
P( C, D, A, B, 3, 16, 0xD4EF3085 );
P( B, C, D, A, 6, 23, 0x04881D05 );
P( A, B, C, D, 9, 4, 0xD9D4D039 );
P( D, A, B, C, 12, 11, 0xE6DB99E5 );
P( C, D, A, B, 15, 16, 0x1FA27CF8 );
P( B, C, D, A, 2, 23, 0xC4AC5665 );

#undef F

#define F(x,y,z) (y ^ (x | ~z))

P( A, B, C, D, 0, 6, 0xF4292244 );
P( D, A, B, C, 7, 10, 0x432AFF97 );
P( C, D, A, B, 14, 15, 0xAB9423A7 );
P( B, C, D, A, 5, 21, 0xFC93A039 );
P( A, B, C, D, 12, 6, 0x655B59C3 );
P( D, A, B, C, 3, 10, 0x8F0CCC92 );
P( C, D, A, B, 10, 15, 0xFFEFF47D );
P( B, C, D, A, 1, 21, 0x85845DD1 );
P( A, B, C, D, 8, 6, 0x6FA87E4F );
P( D, A, B, C, 15, 10, 0xFE2CE6E0 );
P( C, D, A, B, 6, 15, 0xA3014314 );
P( B, C, D, A, 13, 21, 0x4E0811A1 );
P( A, B, C, D, 4, 6, 0xF7537E82 );
P( D, A, B, C, 11, 10, 0xBD3AF235 );
P( C, D, A, B, 2, 15, 0x2AD7D2BB );
P( B, C, D, A, 9, 21, 0xEB86D391 );

#undef F

ctx->state[0] += A;
ctx->state[1] += B;
ctx->state[2] += C;
ctx->state[3] += D;
}

/*
* MD5 process buffer
*/
void md5_update( md5_context *ctx, unsigned char *input, int ilen )
{
int fill;
unsigned long left;

if( ilen <= 0 )
return;

left = ctx->total[0] & 0x3F;
fill = 64 – left;

ctx->total[0] += ilen;
ctx->total[0] &= 0xFFFFFFFF;

if( ctx->total[0] < (unsigned long) ilen )
ctx->total[1]++;

if( left && ilen >= fill )
{
memcpy( (void *) (ctx->buffer + left),
(void *) input, fill );
md5_process( ctx, ctx->buffer );
input += fill;
ilen -= fill;
left = 0;
}

while( ilen >= 64 )
{
md5_process( ctx, input );
input += 64;
ilen -= 64;
}

if( ilen > 0 )
{
memcpy( (void *) (ctx->buffer + left),
(void *) input, ilen );
}
}

static const unsigned char md5_padding[64] =
{
0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

/*
* MD5 final digest
*/
void md5_finish( md5_context *ctx, unsigned char output[16] )
{
unsigned long last, padn;
unsigned long high, low;
unsigned char msglen[8];

high = ( ctx->total[0] >> 29 )
| ( ctx->total[1] << 3 );
low = ( ctx->total[0] << 3 ); PUT_UINT32_LE( low, msglen, 0 );
PUT_UINT32_LE( high, msglen, 4 );

last = ctx->total[0] & 0x3F;
padn = ( last < 56 ) ? ( 56 - last ) : ( 120 - last ); md5_update( ctx, (unsigned char *) md5_padding, padn );
md5_update( ctx, msglen, 8 );

PUT_UINT32_LE( ctx->state[0], output, 0 );
PUT_UINT32_LE( ctx->state[1], output, 4 );
PUT_UINT32_LE( ctx->state[2], output, 8 );
PUT_UINT32_LE( ctx->state[3], output, 12 );
}

/*
* Output = MD5( file contents )
*/
int md5_file( char *path, unsigned char output[16] )
{
FILE *f;
size_t n;
md5_context ctx;
unsigned char buf[1024];

if( ( f = fopen( path, “rb” ) ) == NULL )
return( 1 );

md5_starts( &ctx );

while( ( n = fread( buf, 1, sizeof( buf ), f ) ) > 0 )
md5_update( &ctx, buf, (int) n );

md5_finish( &ctx, output );

fclose( f );
return( 0 );
}

/*
* Output = MD5( input buffer )
*/
void md5_csum( unsigned char *input, int ilen,
unsigned char output[16] )
{
md5_context ctx;

md5_starts( &ctx );
md5_update( &ctx, input, ilen );
md5_finish( &ctx, output );
}

/*
* Output = HMAC-MD5( input buffer, hmac key )
*/
void md5_hmac( unsigned char *key, int keylen,
unsigned char *input, int ilen,
unsigned char output[16] )
{
int i;
md5_context ctx;
unsigned char k_ipad[64];
unsigned char k_opad[64];
unsigned char tmpbuf[16];

memset( k_ipad, 0x36, 64 );
memset( k_opad, 0x5C, 64 );

for( i = 0; i < keylen; i++ )
{
if( i >= 64 ) break;

k_ipad[i] ^= key[i];
k_opad[i] ^= key[i];
}

md5_starts( &ctx );
md5_update( &ctx, k_ipad, 64 );
md5_update( &ctx, input, ilen );
md5_finish( &ctx, tmpbuf );

md5_starts( &ctx );
md5_update( &ctx, k_opad, 64 );
md5_update( &ctx, tmpbuf, 16 );
md5_finish( &ctx, output );

memset( k_ipad, 0, 64 );
memset( k_opad, 0, 64 );
memset( tmpbuf, 0, 16 );
memset( &ctx, 0, sizeof( md5_context ) );
}

static const char _md5_src[] = “_md5_src”;

#ifdef SELF_TEST
/*
* RFC 1321 test vectors
*/
static const char md5_test_str[7][81] =
{
{ “” },
{ “a” },
{ “abc” },
{ “message digest” },
{ “abcdefghijklmnopqrstuvwxyz” },
{ “ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx yz0123456789” },
{ “12345678901234567890123456789012345678901234567890 123456789012” \
“345678901234567890” }
};

static const unsigned char md5_test_sum[7][16] =
{
{ 0xD4, 0x1D, 0x8C, 0xD9, 0x8F, 0x00, 0xB2, 0x04,
0xE9, 0x80, 0x09, 0x98, 0xEC, 0xF8, 0x42, 0x7E },
{ 0x0C, 0xC1, 0x75, 0xB9, 0xC0, 0xF1, 0xB6, 0xA8,
0x31, 0xC3, 0x99, 0xE2, 0x69, 0x77, 0x26, 0x61 },
{ 0x90, 0x01, 0x50, 0x98, 0x3C, 0xD2, 0x4F, 0xB0,
0xD6, 0x96, 0x3F, 0x7D, 0x28, 0xE1, 0x7F, 0x72 },
{ 0xF9, 0x6B, 0x69, 0x7D, 0x7C, 0xB7, 0x93, 0x8D,
0x52, 0x5A, 0x2F, 0x31, 0xAA, 0xF1, 0x61, 0xD0 },
{ 0xC3, 0xFC, 0xD3, 0xD7, 0x61, 0x92, 0xE4, 0x00,
0x7D, 0xFB, 0x49, 0x6C, 0xCA, 0x67, 0xE1, 0x3B },
{ 0xD1, 0x74, 0xAB, 0x98, 0xD2, 0x77, 0xD9, 0xF5,
0xA5, 0x61, 0x1C, 0x2C, 0x9F, 0x41, 0x9D, 0x9F },
{ 0x57, 0xED, 0xF4, 0xA2, 0x2B, 0xE3, 0xC9, 0x55,
0xAC, 0x49, 0xDA, 0x2E, 0x21, 0x07, 0xB6, 0x7A }
};

/*
* Checkup routine
*/
int md5_self_test( void )
{
int i;
unsigned char md5sum[16];

for( i = 0; i < 7; i++ )
{
printf( ” MD5 test #%d: “, i + 1 );

md5_csum( (unsigned char *) md5_test_str[i],
strlen( md5_test_str[i] ), md5sum );

if( memcmp( md5sum, md5_test_sum[i], 16 ) != 0 )
{
printf( “failed\n” );
return( 1 );
}

printf( “passed\n” );
}

printf( “\n” );
return( 0 );
}
#else
int md5_self_test( void )
{
return( 0 );
}
#endif

Làm thử nhé. Đừng kêu đơn giản vội.
Đây là một chuỗi đã được encrypt: 4e11a0651a23437011ee866928ecdd96 (đoán xem nó là zì?)

kidkidChậc riêng kid thì không biết gì rồi. Nhưng mà đã có chương trình giải thuật MD5 rồi thì phải ? Trong cuốn sách ” Cryptography and Network Security ” của William Stallings có nói về decrypt cái này. Anh em chăm sóc thì xem thử .
hailoc12

Để “tiếp lửa” cho đề tài, em đã bỏ công đánh toàn bộ chương 23 (Mã hoá)trong ” Thuật toán 1″ để mọi người có những kiến thức cơ bản về mã hoá. Em nghĩ trước khi nghiên cứu tới mấy cái md5 thì nên tìm hiểu và thành thục các dạng đơn giản đã. Dù sao nếu chỉ mã hoá thông thường thì những thuật toán đó cũng đã đủ rồi, nếu cần bảo mật thật sự thì ta nên dùng có sẵn cho đảm bảo.
[CTDL> Các thuật toán xử lý chuỗi]
http://www.forums.congdongcviet.com/showthread.php?p=14798#post14798

kidkidCái của cậu tớ vừa mới đọc hôm trước. Chậc sao không thấy decrypt nhỉ ? ( tất yếu là không có key rồi ) .
Ada

Mật mã Caesar dùng một phép tính có tính kết hợp và giao hoán trên bảng 26 chữ cái (gọi là nhóm C26). Bảng tính của nó như thế này:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Qui tắc dùng bảng tính: x + y = tra bảng dòng x, cột y

Mình xin đóng góp một phép tính khác trên bảng 26 chữ cái, không có tính giao hoán nhưng có tính kết hợp, có tên là nhóm D13, như thế này:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M A O P Q R S T U V W X Y Z N
C D E F G H I J K L M A B P Q R S T U V W X Y Z N O
D E F G H I J K L M A B C Q R S T U V W X Y Z N O P
E F G H I J K L M A B C D R S T U V W X Y Z N O P Q
F G H I J K L M A B C D E S T U V W X Y Z N O P Q R
G H I J K L M A B C D E F T U V W X Y Z N O P Q R S
H I J K L M A B C D E F G U V W X Y Z N O P Q R S T
I J K L M A B C D E F G H V W X Y Z N O P Q R S T U
J K L M A B C D E F G H I W X Y Z N O P Q R S T U V
K L M A B C D E F G H I J X Y Z N O P Q R S T U V W
L M A B C D E F G H I J K Y Z N O P Q R S T U V W X
M A B C D E F G H I J K L Z N O P Q R S T U V W X Y
N Z Y X W V U T S R Q P O A M L K J I H G F E D C B
O N Z Y X W V U T S R Q P B A M L K J I H G F E D C
P O N Z Y X W V U T S R Q C B A M L K J I H G F E D
Q P O N Z Y X W V U T S R D C B A M L K J I H G F E
R Q P O N Z Y X W V U T S E D C B A M L K J I H G F
S R Q P O N Z Y X W V U T F E D C B A M L K J I H G
T S R Q P O N Z Y X W V U G F E D C B A M L K J I H
U T S R Q P O N Z Y X W V H G F E D C B A M L K J I
V U T S R Q P O N Z Y X W I H G F E D C B A M L K J
W V U T S R Q P O N Z Y X J I H G F E D C B A M L K
X W V U T S R Q P O N Z Y K J I H G F E D C B A M L
Y X W V U T S R Q P O N Z L K J I H G F E D C B A M
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Cách dùng bảng tính: như trên.

saobang86ww

bài viết cũng được. bạn có thể cài đặt thuật toán RSA, elgamal bằng C++ hoặc pascal?
nếu được bạn liên hệ với mình qua email: [email protected]

dangx

_Chắc hẳn anh em đã biết về phương pháp này. Vì nó có lịch sử lâu đời và nổi tiếng.

Khóa dùng theo cột, tức là sẽ chia plain-text thành mảng 2 chiều trong đó số cột chính là key. Cipher-text thu được bằng cách lấy các cột từ trên xuống dưới cho đến khi hết. Vì vậy phương pháp này làm việc tương đương với các thao tác
trên ma trận .

Ví dụ : Với key = 5 tức là sẽ phải chia thành 5 cột ; giả sử
plaintext = “Pete writes the code”
thì chia thành

1 2 3 4 5
———————
P e t e w
r i t e s
t h e c o
d e
———————

vậy nếu lấy hết từng cột và gom hết thông tin lại ta có
ciphertext = “prtdeihetteeecwso”

http://i177.photobucket.com/albums/w233/pete87_photo/Tran_Cipher_5.jpg

Download Program (http://www.freewebtown.com/lttram/programming/Tran_Cipher_5.exe)

^^’….Sao không ai tham gia nhỉ ??

Link die hết rồi

clamvn

Định viết 1 chương trình giải mã cho mấy pác xem thử, nhưng mà suy đi tính lại thấy giải mã thì cũng chả khác j mã hóa vì thuật toán biết hết rồi -> không còn gì là thú vị nữa.
Sao chúng ta không tổ chức một cuộc thi xem ai là người tìm ra phương pháp mã hóa hay nhất, hữu hiệu nhất nhỉ. Cái này hay đấy. Mấy bác admin làm tiên phong đi 🙂
À, làm sao biết cái tụi “be hacked” mã hóa kiểu gì mà mình decrypt nhỉ. Hay là mò kim đáy hồ, cứ thử hết các phương pháp rùi cũng đúng 1 cái. Khó hỉu quá !!!

Gà. Không biết thì ngồi nghe, nói bậy nói bạ người ta cười.
Ông tưởng decrypt nó cho ông cái key để ông làm à.
Key cũng có 2 loại :private và public. chưa nói đến độ phức tạp của key và độ phức tạp khi dung key dể decrypt.

Để hack 1 cái gì đó thì phải là pro về crypt rồi. Luôn có nhưng cách test đẻ thử xem mật mã thuộc loại nào, kiểu nào để thu hẹp .
ông nghĩ nó ngồi dùng lệnh for chắc ?(:X)

Em nghe nói trong chiến tranh thế giới thứ II ông toán học Anh gì ấy đã chế tạo ra máy giải mã, có thể giải được hầu hết các kiểu mã hoá của Đức bấy giờ. Chỉ tiếc sau đó biết nhiều quá nên ông ấy bị chính phủ khử. Nhưng không biết nguyên lý của cái máy ấy thế nào

Cái cách mã hóa trong chiến tranh thế giới II là ko thể phá khi ko có key (vì phạm vi xử lý quá lớn )
Chiến vì vậy mà trong chiến tranh thế giới II ,điệp viên rất nhiều để lấy dc cái key.
Cách mã hóa này nghe thôi cũng nhức cái đầu, chưa nó sau đó dùng key để decrypt 😀

Ada

Nhân dịp thấy cái chủ đề ‘crypto’ cũ này được bới lên, mình cũng xin đóng góp 1 thuật toán mật mã hóa hoàn chỉnh.

Nó là 1 mã cụm đối xứng với những đặc điểm như sau.

— Là một mã hướng từ (word-oriented), nghĩa là chỉ làm việc trên các từ máy với một độ dài w (bit) thống nhất. Trong C các từ được thực hiện bằng các kiểu unsigned (char, short, long, long long…), tức là điển hình w=8, 16, 32, 64,… Nó có độ dài cụm rõ và cụm mã 4w bit, độ dài khóa 5w bit, và còn có 2 khóa phụ nữa với dài tổng cộng 5w bit.

— Không dùng các bảng thế (s-box) và thậm chí không dùng một hằng số bí ẩn (magic number) nào cả. Chỉ dùng thuần túy các phép tính luận lí & số học có sẵn của bộ vi xử lí, như phép cộng, nhân, xor và hoán vị trên từ.

Nhờ vậy, nó rất nhanh, rất minh bạch và rất dễ dàng lập trình để chạy trong thời gian hằng (constant time). Nên biết rằng các thuật toán mật mã dùng bảng thế hay hằng số bí ẩn (chẳng hạn như DES và AES) thường gây ra nghi ngờ rằng có thể chúng ẩn giấu những cửa sau (back door), tức là những công thức bí mật nào đó do tác giả cố tình cài vào thuật toán để giúp cho việc phá khóa dễ dàng. Các thuật toán như thế cũng thường dẫn đến phương pháp cài đặt hiệu quả duy nhất là lấy giá trị của dữ liệu làm chỉ số truy xuất mảng trong bộ nhớ RAM. Một cài đặt như thế, dưới ảnh hưởng của cache, sẽ có thời gian chạy biến thiên theo giá trị của dữ liệu, nghĩa là thời gian chạy tiết lộ thông tin về dữ liệu. Cài đặt như thế rất dễ bị tổn thương bởi các kĩ thuật thám mã đo thời gian (timing attacks).

(còn tiếp)

Ada

(tiếp theo)

Các phép toán cần thiết. Mình sẽ dùng các ký hiệu phép toán \oplus (xor), + (cộng), – (trừ), * (nhân), / (chia) để chỉ các phép tính luận lí và số học tương ứng của ngôn ngữ C (mà thực chất chúng là phép tính của ngôn ngữ máy, ngôn ngữ “tự nhiên” của bộ vi xử lí). Cần nhấn mạnh rằng các phép cộng, trừ và nhân trong ngôn ngữ C khác với trong toán học thông thường ở chỗ chúng thực hiện trên các số nguyên modulo 2^w (w là độ dài từ máy), nghĩa là chúng đều xác định trên một tập hữu hạn các giá trị biểu diễn được bằng w bit.

Phép cộng là một phép toán có phép toán ngược: với a, b bất kì, tồn tại duy nhất b’ để

a+b+b’=a

Ta đã biết rằng b’=-b (thường gọi là số đối của b). Vì thế ta nói phép toán ngược của phép cộng là phép trừ.

Tương tự, phép xor cũng có phép toán ngược: với a, b bất kì, tồn tại duy nhất b’ để

a \oplus b \oplus b’=a

Vì biết b’=b, ta nói phép toán ngược của xor chính là xor.

Khác với phép cộng modulo 2^w, phép nhân modulo 2^w không có phép toán ngược. Thật vậy, b’ thỏa a \ast b \ast b’=a với mọi a chỉ tồn tại (và duy nhất) khi b và 2^w nguyên tố cùng nhau, hay nói cách khác b phải là một số lẻ. Với số b như thế, b’ gọi là số nghịch đảo của b và được kí hiệu là \frac{1}{b} và ta cũng có thể viết \frac{a \ast b}{b}=a, tức là mặc nhiên xem phép toán \frac{(.)}{(.)} (chú ý: không phải là phép chia của ngôn ngữ C) như “phép toán” ngược của phép nhân. Nhưng cần nhớ rằng “phép toán” ngược này thật ra không phải là phép toán bởi nó chỉ xác định với một số giá trị của b.

(còn tiếp)

Ada

(tiếp theo)

Phức tạp hơn hẳn phép xor và phép cộng, trong khi thời gian thực hiện trên bộ vi xử lí chỉ ngang với hai phép toán kia, phép nhân là một công cụ tuyệt vời để xây dựng các mật mã hiệu quả trên phần mềm. Nhưng việc không có phép toán ngược là một trở ngại: nếu mã hóa a bằng cách nhân a với khóa (vốn dĩ có thể có giá trị bất kì) thì có thể không tồn tại giá trị khóa nghịch đảo để giải mã.

Tuy vậy, đoạn trên đã gợi í một cách đơn giản để cải tiến phép nhân thành một phép toán mới có phép toán ngược, mà thực chất là phép nhân các số lẻ mod 2^{w+1} biểu diễn dưới dạng các số bất kì (lẻ hay chẵn) mod 2^w. Cho hai số w bit bất kì a và b, tích cải tiến của chúng, kí hiệu bởi a \cdot b, là một số w bit được định nghĩa như sau.

1. Nối thêm một bit với giá trị 1 vào tận cùng của a, được a1. Và cũng làm như thế với b, được b1.

2. Nhân a1 với b1 modulo 2^{w+1}, được c1.

3. Bỏ bớt bit tận cùng của c1 (vốn dĩ luôn có giá trị là 1), được c. Đó chính là tích cần tìm.

Phép tính theo định nghĩa nói trên đòi hỏi số học w+1 bit không có trên bộ vi xử lí, nên chỉ có tính lí thuyết. Nhưng từ định nghĩa đó, ta có ngay

a \cdot b = ((2a+1)(2b+1)-1)/2 = 2ab + a + b

Như vậy, công thức thực tế, hiệu quả để tính a \cdot b bằng bộ vi xử lí, là

a \cdot b = 2 \ast a \ast b + a + b

hoặc

a \cdot b = a \ast (2 \ast b + 1) + b
a \cdot b = b \ast (2 \ast a + 1) + a

(còn tiếp)

Ada

(tiếp theo)

Phép nhân cải tiến nói trên đóng vai trò trung tâm trong thuật toán mật mã nên ở đây mình xin dừng lại một chút để nêu vài tính chất quan trọng của nó. Trước hết, tính kết hợp:

(a \cdot b) \cdot c = a \cdot (b \cdot c)

Chính nhờ tính kết hợp mà mình có thể thản nhiên viết a \cdot b \cdot c mà không cần phải viết rõ các dấu ngoặc để thể hiện trình tự thực hiện 2 phép tính nhân.

Thứ nữa, tính giao hoán:

a \cdot b = b \cdot a

Ta đã biết rằng 1 là phần tử đơn vị của phép nhân trong ngôn ngữ C, nghĩa là với a bất kì:

1 \ast a = a = a \ast 1

Từ đó, dễ thấy rằng, đối với phép nhân cải tiến thì phần tử đơn vị là 0:

0 \cdot a = a = a \cdot 0

Ta đã biết rằng, đối với phép nhân trong ngôn ngữ C, mọi số lẻ a đều có nghịch đảo, tức số \frac{1}{a} thỏa a \ast \frac{1}{a}=1. Sau vài biến đổi đơn giản, có thể chứng minh được rằng đối với phép nhân cải tiến, mọi a đều có nghịch đảo (tức a’ thỏa a \cdot a’ = 0) là

a’ = -\frac{a}{2a + 1}

Nói cách khác, a’ bằng số đối của a nhân với \frac{1}{2a+1}, vốn dĩ tồn tại với mọi a. Và từ giờ về sau, ta sẽ chính thức sử dụng dấu nháy đơn ( ‘ ) để kí hiệu cho phép nghịch đảo này.

Mình đã nói chưa nhỉ? Tốt nhất vẫn nên nhắc lại lần nữa rằng phép nhân cải tiến này có phép toán ngược. Nhưng ta sẽ không đặt ra thêm một cái tên nữa, như là “phép chia cải tiến”, cho phép toán ngược này. Và cũng không đặt ra thêm kí hiệu nào nữa. Muốn thực hiện phép toán ngược thì cứ nhân với nghịch đảo thôi:

a \cdot b \cdot b’ = a

Những ai đã tìm hiểu những thuật toán mật mã thực sự như là DES hẳn biết rõ một tính chất được gọi là tính bù (complementation property):

\mathrm{DES}(\neg X, \neg Z) = \neg \mathrm{DES}(X, Z)

Trong đó X là cụm rõ, Z là khóa, \neg kí hiệu phép tính phần bù luận lí, hay còn gọi là phủ định từng bit, được viết là ~ trong ngôn ngữ C, và có thể được tính bởi a \oplus (\neg a) = -1. Và tính bù này thực chất là mã của các phần bù bằng phần bù của mã.

Phép nhân cải tiến của ta cũng có một tính chất gần giống như tính bù, thể hiện như sau:

(\neg a) \cdot b = \neg(a \cdot b)

Nếu xem a \cdot b như một thứ bội số của a, hệ thức này nói rằng bội của một phần bù bằng phần bù của bội. Hay nói cách khác, qua phép nhân cải tiến, phần bù luận lí được bảo toàn. Trong thiết kế mật mã, mọi tính chất đại số nào không cần thiết như tính kết hợp, tính giao hoán, tính bù,… đều là không đáng mong muốn bởi vì có thể bị đối phương lợi dụng để thám mã. Đó là lí do khiến ta không thể sử dụng phép nhân cải tiến một cách trực tiếp, mà chỉ dùng nó như là phép toán trung tâm để xây dựng một phép toán khác thích hợp hơn.

(còn tiếp)

Ada

(tiếp theo)

Thêm một phép đổi dấu toán hạng bên trái và một phép đổi dấu kết quả phép nhân cải tiến, ta sẽ định nghĩa được một phép toán mới, kí hiệu là \times:

a \times b = -((-a) \cdot b)

Dễ thấy rằng ta cũng có

a \cdot b = -((-a) \times b)

Trên bộ vi xử lí, phép toán \times này có thể tính được một cách nhanh chóng không kém gì phép nhân cải tiến ở trên:

a \times b = 2ab + a – b

Do sự đổi dấu, phép toán \times không giao hoán, cũng không kết hợp. Nhưng nó có một tính chất gần giống như tính kết hợp:

(a \times b) \times c = a \times (b \cdot c)

Vì thế nó vẫn có phép toán ngược nhờ đó mà ta có thể dùng nó để mã hóa và giải mã thông tin:

(a \times b) \times b’ = a

Trong đó b’ là nghịch đảo của b qua phép toán \cdot đã định nghĩa ở trên.

Do tính chất “tựa kết hợp” của \times và tính giao hoán của \cdot nên \times cũng có một tính chất gần giống như tính giao hoán:

(a \times b) \times c = (a \times c) \times b

Từ đó, khi mã hóa hai bản rõ a và a \times b (mà ta có thể xem là một thứ bội số của a) bằng cùng một khóa c, ta sẽ được hai bản mã tương ứng a \times c và (a \times c) \times b, tức là mã của bội bằng bội của mã. Nói cách khác, nếu xem b như là tỉ số của hai bản rõ thì qua phép toán \times, tỉ số bản rõ được bảo toàn trong bản mã.

Với a bất kì, giá trị 1 – a được gọi là phần bù số học của a. Tương tự như tính bù ở phép nhân cải tiến, qua phép toán \times, phần bù số học được bảo toàn, nghĩa là bội của phần bù bằng phần bù của bội:

(1-a) \times b = 1 – (a \times b)

Cũng như tính bảo toàn phần bù luận lí, tính bảo toàn phần bù số học cũng là một tính chất không đáng mong muốn, nhưng \times vẫn được xem là một phép toán thích hợp cho mật mã hơn \cdot bởi vì ngoài việc nó không có tính kết hợp hay tính giao hoán, như ta sẽ thấy về sau, trong mật mã nó được dùng xen kẽ với các phép hoán vị bit và các phép xor, vốn dĩ là những phép toán bảo toàn phần bù luận lí nhưng không bảo toàn phần bù số học. Qua một hợp thành phức tạp các phép toán không tương thích với nhau như thế thì chắc là không một thuộc tính nào có thể bảo toàn.

Sự không tương thích giữa các phép toán không phải chỉ xét trên tính bảo toàn phần bù này nọ, mà xét trên rất nhiều phương diện khác nhau. Có thể dễ dàng thử nghiệm rằng, chẳng hạn, giữa phép \times và phép xor không tồn tại những hệ thức đơn giản nào tương tự như tính phân phối của phép nhân với phép cộng. Hơn thế nữa, người ta đã chứng minh được rằng, trái với phép \times, phép xor và phép quay không thể biểu diễn bằng một đa thức trên vành số nguyên modulo 2^w, nghĩa là hai phép toán này không thể thực hiện được, cho dù chỉ trên lí thuyết, bằng các phép nhân và các phép cộng của ngôn ngữ C.

(còn tiếp)

Ada

(tiếp theo)

Trong một phép cộng hay phép nhân, giá trị bit 0 của toán hạng có ảnh hưởng không những đến giá trị bit 0 mà còn ảnh hưởng đến giá trị các bit 1, 2, 3,… của kết quả; nhưng bit 1 của toán hạng chỉ có thể ảnh hưởng đến bit 1, 2, 3,… mà không thể ảnh hưởng đến bit 0 của kết quả, còn bit 2 của toán hạng thì chỉ có thể ảnh hưởng đến bit 2, 3, 4,… mà không thể ảnh hưởng đến bit 0 và bit 1 của kết quả. Nói một cách tổng quát thì trong một phép cộng hay phép nhân, giá trị bit k của toán hạng chỉ ảnh hưởng đến giá trị bit k và các bit cao hơn k (nếu có) của kết quả. Như thế, bit càng thấp của toán hạng thì có ảnh hưởng đến càng nhiều bit của kết quả và bit càng cao của kết quả thì chịu ảnh hưởng của càng nhiều bit của toán hạng.

Một tiêu chí bắt buộc để mật mã có thể bảo mật là mỗi bit của cụm rõ phải có ảnh hưởng đến tất cả các bit của cụm mã (và hệ quả là mỗi bit của cụm mã phải lệ thuộc vào tất cả các bit của cụm rõ). Một mật mã chỉ sử dụng toàn các phép cộng, phép nhân và phép xor không thể đáp ứng tiêu chí này.

Do vậy, không có gì lạ khi trong những mật mã chỉ dùng thuần túy các phép tính luận lí và số học của máy không thể vắng mặt những phép hoán vị các bit của một từ, như các phép dịch và các phép quay. Những hoán vị như thế có tác dụng đưa các bit cao ở đầu ra (kết quả) của môt phép cộng hay phép nhân xuống thấp trước khi dẫn đầu ra ấy đến đầu vào (toán hạng) của một phép cộng hay phép nhân nào đó tiếp theo.

Phép hoán vị sẽ dùng trong thuật toán mật mã giới thiệu ở đây là phép hoán đổi nửa thấp với nửa cao của một từ, nghĩa là phép quay một số w bit đi w/2 bit sang bên trái (hay bên phải), được kí hiệu là S theo lối hậu tố. Ví dụ, trên các từ 8 bit:

\mathrm {0x5a ^S = 0xa5}

Và trên các từ 32 bit:

\mathrm {0x1234abcd ^S = 0xabcd1234}

Phép quay không phải chỉ đơn giản là một công cụ thực tiễn để “trộn đều” các bit ở mọi vị trí với nhau mà còn có một cơ sở lí thuyết vững chắc. Người ta đã chứng minh được rằng phép cộng và phép quay tạo thành một bộ hàm cơ sở đủ, nghĩa là ít ra trên lí thuyết, chúng có thể thực hiện bất kì hàm nào trên w bit. Trong khi đó, các bộ phép toán khác thiếu vắng phép quay hay phép cộng (hoặc phép nhân), như {xor, quay}, {cộng, xor}, {nhân, xor}, {cộng, nhân, xor},… đều không có được tính đủ như thế.

(còn tiếp)

Ada

(tiếp theo)

Phác thảo thuật toán. Đoạn này sẽ chỉ ra thuật toán mã hóa ở dạng sơ khai. Cuối đoạn này sẽ nêu ra vài nhược điểm của thuật toán sơ khai này. Việc khắc phục những nhược điểm đó bằng một thuật toán hoàn chỉnh sẽ được trình bày ở đoạn sau.

Phép nhân \times và phép hoán vị hai nửa từ \mathrm ^S kết hợp với nhau tạo ra sức mạnh bảo mật của thuật toán trong một hàm gọi là hàm G. Hàm G mã hóa một từ văn bản x bằng hai từ khóa z_0 và z_1 bằng cách lặp liên tiếp hai vòng, mỗi vòng gồm một phép \times theo sau là một phép \mathrm ^S:

G(x, z_0, z_1) = ((x \times z_0)\mathrm{^S} \times z_1)\mathrm {^S}

Để mã hóa, trước tiên cụm rõ X với độ dài 4w bit được chia thành 4 từ w bit và nạp vào 4 thanh ghi văn bản x_0, x_1, x_2, x_3:

(x_0,x_1,x_2,x_3) \leftarrow X

Ở đây và về sau, kí pháp xâu (hay còn gọi là kí pháp con số) chẳng hạn như x_0 x_1 x_2… sẽ ngụ í thứ tự từ cao đến thấp, nghĩa là nếu xâu ấy là một số nhiều phần thì x_0 là phần cao nhất (có nghĩa nhất), x_1 là phần thấp hơn kế tiếp, x_2 là phần thấp hơn nữa, v.v.; kí pháp bộ (hay còn gọi là kí pháp vector) chẳng hạn như (x_0,x_1,x_2,…) ngụ í thứ tự từ thấp đến cao, nghĩa là nếu bộ ấy là một số nhiều phần thì x_0 sẽ chứa phần thấp nhất của số ấy, x_1 phần cao hơn kế tiếp x_0, và x_2 là phần cao hơn kế tiếp x_1, v.v. Hai kí pháp này là ngược nhau. Chẳng hạn, ta luôn có (a,b,c,d) = d c b a. Các phần không nhất thiết có cùng chiều dài. Chẳng hạn, ta luôn có \text{0x9876543210} = (\text{0, 0x21, 0x543, 0x9876}).

Tương tự như vậy, khóa Z với độ dài 5w bit được chia thành 5 từ w bit và nạp vào 5 thanh ghi khóa z_0, z_1, z_2, z_3, z_4:

(z_0,z_1,z_2,z_3,z_4) \leftarrow Z

Trong quá trình mã hóa, các thanh ghi văn bản và các thanh ghi khóa sẽ được biến đổi. Kết quả của quá trình mã hóa thực chất là giá trị cuối cùng của 4 thanh ghi văn bản, mà cụm mã Y với độ dài 4w được tạo thành từ đó:

Y \leftarrow (x_0,x_1,x_2,x_3)

(còn tiếp)

Ada

(tiếp theo)

Quá trình mã hóa thực sự là tiến hành 32 lần lặp đi lặp lại, thuật ngữ gọi là 32 vòng, một trong hai động tác mà ta sẽ gọi tên là A và B, theo thứ tự lần lượt là đầu tiên 8 vòng loại A, sau đó 8 vòng loại B, tiếp đó lại 8 vòng loại A, cuối cùng lại 8 vòng loại B.

Sau mỗi vòng, các thanh ghi văn bản được hoán vị vòng quanh, nghĩa là nạp thanh ghi x_{0} bằng nội dung của thanh ghi x_{1} và đồng thời, x_{1}, bằng x_{2}, x_{2} bằng x_{3}, x_{3} bằng x_{0} :

(x_0,x_1,x_2,x_3) \leftarrow (x_1,x_2,x_3,x_0)
Mỗi vòng đọc thanh ghi z_{3} hai lần và sau mỗi lần cả 5 thanh ghi khóa lại được hoán vị vòng quanh:

(z_0,z_1,z_2,z_3,z_4) \leftarrow (z_2,z_3,z_4,z_0,z_1)

Vì thế ta đọc ra được hai từ khóa độc lập với nhau, z_{3} và z_{3}’=z_{4}. Mỗi từ khóa này đi thẳng vào một vòng (con) của hàm G. Bằng hai từ khóa đó, G mã hóa từ văn bản x_{0} và “trộn” (xor) từ này vào một từ văn bản khác.

Ở vòng loại A, mã hóa x_0 rồi trộn nó vào x_1:

x_0 \leftarrow G(x_0, z_3, z_3′)
x_1 \leftarrow x_1 \oplus x_0

Còn ở vòng loại B, trộn x_0 vào x_3 trước rồi mới mã hóa x_0:

x_3 \leftarrow x_3 \oplus x_0
x_0 \leftarrow G(x_0, z_3, z_3′)

(còn nữa)

Ada

(tiếp theo)

Nhược điểm rõ rệt nhất của thuật toán sơ khai này nằm ở cách dùng phép nhân.

Phép toán \times có tính chất là x \times 0 = x với mọi x. Nếu một từ khóa trong một phép toán \times nào đó trong thuật toán có giá trị bằng 0 thì \times chỉ có tác dụng đơn thuần là sao chép mọi từ rõ trên đầu vào của nó thành từ mã ở đầu ra, nghĩa là khi đó nó hoàn toàn không mã hóa.

Hàm G(x, z_0, z_1), vốn dĩ dùng để mã hóa từ văn bản bằng hai từ khóa, có hai phép \times mỗi phép có một hoán vị S đi theo. Nhưng nếu cả hai từ khóa đều bằng 0 thì G cũng giống như \times, hoàn toàn không mã hóa:

G(x, 0, 0) = x

Thuật toán có cả thảy 64 phép toán \times, mỗi phép dùng một từ của khóa Z vốn dĩ có 5 từ. Vậy mỗi từ của khóa Z được dùng một cách trực tiếp lặp đi lặp lại 12 đến 13 lần. Chỉ cần một từ khóa bằng 0 thì đã có 12 đến 13 phép toán \times bị mất tác dụng mã hóa. Càng nhiều từ khóa bằng 0, tác dụng mã hóa của thuật toán càng yếu. Trong trường hợp xấu nhất, Z = 0, mọi phép \times (và mọi phép \mathrm{^S}) đều mất tác dụng mà chỉ còn trơ lại các phép xor. Khi đó mỗi từ của cụm mã sẽ chỉ còn là một tổ hợp tuyến tính của các từ của cụm rõ, tức là một giá trị có dạng

Y_i = a_{i0} X_0 \oplus a_{i1} X_1 \oplus a_{i2} X_2 \oplus a_{i3} X_3

Trong đó i = 0, 1, 2, 3, với Y = Y_3 Y_2 Y_1 Y_0 và X = X_3 X_2 X_1 X_0, và các hệ số a_{i0}, a_{i1}, a_{i2}, a_{i3} nhận giá trị 0 hoặc 1.

Mật mã tuyến tính như thế sẽ bị phá trong nháy mắt: chỉ cần biết khoảng hơn một cặp giá trị (X,Y) thôi thì ta đã có thể lập được đầy đủ một hệ phương trình bậc 1 để tìm ra khóa Z rồi.

Tóm lại, thuật toán sơ khai này có nhược điểm thứ nhất là có những khóa yếu, tức là những giá trị khóa mà hễ được dùng sẽ cho phép phá khóa dễ dàng hơn hẳn.

(còn tiếp)

Ada

(tiếp theo)

Nhược điểm thứ hai của thuật toán sơ khai này, nói đúng ra thì là của mọi mật mã cụm, nằm ở tính chất cụm. Giá trị của cụm mã Y chỉ phụ thuộc vào giá trị của cụm mã X và khóa Z. Phương thức mã hóa chia bản rõ thành từng cụm rồi dùng khóa mã hóa từng cụm một cách độc lập với nhau trong kĩ thuật mật mã gọi là chế độ sổ mã điện tử (Electronic Code Book), viết tắt là ECB. Nếu dùng Z để mã hóa một bản rõ có những giá trị cụm nào đó xuất hiện nhiều lần thì những giá trị cụm mã tương ứng cũng xuất hiện nhiều lần ở vị trí tương ứng trong bản mã, dẫn đến tiết lộ một phần thông tin về bản rõ.

Ví dụ trực quan nhất là bản rõ và bản mã ECB của một tấm ảnh chim cánh cụt có thể tìm thấy ở nhiều địa chỉ trên mạng, chẳng hạn http://www.tegos.pt/en/know_more.html

Cả hai nhược điểm nói trên ở thuật toán sơ khai đều có thể khắc phục.

— Để khắc phục nhược điểm thứ hai, ta sẽ đưa vào thuật toán một tham số nữa gọi là nắn (tweak). Đây là thuật ngữ để chỉ một tham số lệ thuộc vào vị trí cụm, hay nói cách khác, giá trị của nó biến đổi theo số thứ tự của từng cụm trong bản rõ. Hiển nhiên là khi giá trị cụm mã lệ thuộc cả vào số thứ tự của cụm thì hai cụm rõ dù có bằng nhau cũng mã hóa thành hai giá trị “độc lập” với nhau và nhờ đó, khắc phục được nhược điểm thứ hai.

Việc làm cho cụm mã lệ thuộc vào số thứ tự của cụm, hơn là vào giá trị của các cụm rõ hay cụm mã lân cận, sẽ tạo điều kiện hoàn toàn cho truy nhập ngẫu nhiên, nghĩa là không những ta có thể ứng dụng thuật toán này để mã hóa tệp tin lưu trữ hay mã hóa gói tin truyền qua mạng mà còn có thể ứng dụng nó vào các việc cao cấp hơn như mã hóa cơ sở dữ liệu hay mã hóa ổ đĩa cứng. Hơn nữa, khả năng truy nhập ngẫu nhiên cũng đồng nghĩa với khả năng mã hóa đồng thời nhiều cụm trên những kiến trúc hiện đại như máy tính đa xử lí, bộ vi xử lí đa lõi và bộ xử lí vector, để tăng tốc độ mã hóa lên nhiều lần.

— Để khắc phục nhược điểm thứ nhất, ta sẽ đưa vào thuật toán một tham số nữa gọi là khóa đơn vị (unit key) điều khiển việc lựa chọn phần tử đơn vị cho từng phép toán \times. Điều này nghe có vẻ hơi lạ bởi vì như ta biết ở trên, phần tử đơn vị là 0, một giá trị cố định. Nhưng việc này thật sự có thể làm được, bằng cách đa dạng hóa phép nhân (phép toán \cdot và phép toán \times tương ứng), nghĩa là tổng quát hóa nó thành một họ các phép toán với những phần tử đơn vị là tham số mà ta có thể chọn một cách tùy thích. Cứ mỗi giá trị chọn cho phần tử đơn vị sẽ cho ta một dị bản mới của phép toán này. Khi mã hóa, 64 phép \times trong thuật toán sẽ được chọn với 64 giá trị khác nhau của phần tử đơn vị, theo sự điều khiển của khóa đơn vị.

Một phép \times bị mất tác dụng mã hóa khi từ khóa được dùng có giá trị bằng đơn vị. Dễ thấy rằng trong trường hợp xấu nhất, là khi mỗi từ trong 5 từ của khóa Z đều (chẳng may) được dùng trong một phép \times với đơn vị bằng chính nó, thì cũng chỉ 5 phép \times như thế bị vô hiệu và ta vẫn còn lại 59 phép \times khác có tác dụng. (Trường hợp xấu nhất này xảy ra với xác suất 2^{-5w}, tức là ngang với khả năng tìm mò khóa chỉ thử một phát trúng ngay.) Nhờ đó, nhược điểm thứ nhất được khắc phục.

(còn tiếp)

Ada

(tiếp theo)

Đa dạng hóa phép nhân cải tiến. Giả sử e là một số w bit cố định bất kì. Trên tập hợp các số w bit, ta định nghĩa hai phép toán mới, kí hiệu là \odot và \otimes, như sau.

a \odot b = (a-e)\cdot(b-e) + e
= 2ab + (1 – 2e)(a + b – e)

a \otimes b = -((-a) \odot b)
= 2ab + (1 – 2e)(a – b + e)

Do tính chất đối hợp của phép đổi dấu (một phép toán một ngôi đối hợp là một phép toán khác ánh xạ đồng nhất và là phép toán ngược của chính nó) ta cũng có 2 hệ thức khác có thể dùng làm định nghĩa một cách tương đương.

a \otimes b = (a+e) \times (b-e) – e

a \odot b = -((-a) \otimes b)

Có thể chứng minh được rằng trên tập hợp các số w bit, các đa thức ba biến nằm ở vế phải của những hệ thức định nghĩa nói trên là những đa thức hoán vị, nghĩa là khi được xem như những hàm số của bất cứ biến nào khi cố định hai biến còn lại ở giá trị bất kì, chúng sẽ là những song ánh.

Có thể dễ dàng chứng minh rằng giống như \cdot phép toán \odot cũng có tính kết hợp, tính giao hoán, có phần tử đơn vị là e, và trên phép toán này mọi giá trị a đều có nghịch đảo, kí hiệu a^{-1}, với giá trị là

a^{-1} = (a – e)’ + e
= \frac{(2e – 1) a – 2e(e-1)}{2(a-e) + 1}

Nhờ đó mà ta có thể dùng \odot để mã hóa và giải mã

a \odot b \odot b^{-1} = a

Nhưng ta sẽ không dùng \odot, mà dùng dạng cải biên của nó là \otimes, vốn dĩ không kết hợp hay giao hoán

(a \otimes b) \otimes b^{-1} = a

Nhưng cần nhớ rằng \otimes, vốn là dạng tổng quát hóa của \times, cũng như \times, có tính tựa kết hợp:

(a \otimes b) \otimes c = a \otimes (b \odot c)

và tựa giao hoán:

(a \otimes b) \otimes c = (a \otimes c) \otimes b

(Trong đó, \otimes và \odot có cùng đơn vị e.)

Ở đây, có lẽ nên mở ngoặc chú thích rằng \cdot và \odot trong toán học thường không được xem như các phép toán mới, mà chỉ là một cách biểu diễn khác của phép nhân các số lẻ modulo 2^{w+1} mà thôi. Nói một cách hình thức, gọi \mathbb{Z}(n) là tập các số nguyên modulo n và \mathbb{Z}_{1}(2^w) là tập các số nguyên lẻ modulo 2^w thì đại số (\mathbb{Z}_{1}(2^{w+1}), \ast, \frac{1}{(.)}, 1), đại số ( \mathbb{Z}(2^w), \cdot, (.)’, 0) và đại số ( \mathbb{Z}(2^w), \odot, (.)^{-1}, e) là những nhóm đẳng cấu với nhau, nghĩa là tồn tại một song ánh, gọi là phép đẳng cấu, từ tập hợp này đến tập kia qua đó mọi phép toán trên những phần tử nào đó của nhóm này có thể thực hiện nhờ phép toán tương ứng trên những phần tử tương ứng của nhóm kia:

— Phép đẳng cấu \mathbb{Z}(2^w) \rightarrow \mathbb{Z}(2^w) định nghĩa bởi x \mapsto x – e, nhờ đó đơn vị e ứng với đơn vị 0, giúp ta tính nghịch đảo (.)^{-1} nhờ phép nghịch đảo (.)’, giúp ta thực hiện phép nhân \odot nhờ phép nhân \cdot; và

— Phép đẳng cấu \mathbb{Z}(2^w) \rightarrow \mathbb{Z}_{1}(2^{w+1}) định nghĩa bởi x \mapsto 2 \ast x + 1, nhờ đó đơn vị 0 ứng với đơn vị 1, giúp ta tính nghịch đảo (.)’ nhờ phép nghịch đảo \frac{1}{(.)} và giúp ta thực hiện phép nhân \cdot nhờ phép nhân \ast của ngôn ngữ C.

Nếu chọn cho \odot một đa thức định nghĩa tổng quát hơn một chút, ta còn có thể tạo ra những nhóm hoàn toàn khác, không đẳng cấu với các nhóm trên. Ví dụ, ta có thể tạo ra nhóm cyclic, tức nhóm đẳng cấu với (\mathbb{Z}(2^w), +, -(.), 0). Tuy vậy, phép nhân trong những nhóm như thế tính toán phức tạp mà độ bảo mật không cao nên về mặt công nghệ là kém hiệu quả. Ta sẽ không quan tâm đến chúng.

Ta đã biết rằng phép toán \times (mà có thể xem là một trường hợp riêng của \otimes, với e = 0) bảo toàn phần bù số học. Tính chất này cũng có ở phép toán \otimes với e bất kì, nhưng dĩ nhiên ở dạng tổng quát hơn:

(1 – 2e – a) \otimes b = 1 – 2e – (a \otimes b)

Nói cách khác, khi dùng cùng một khóa b mã hóa hai từ rõ a_1, a_2 có quan hệ a_1 + a_2 = 1-2e thì thu được hai từ mã cũng có quan hệ này. Mối quan hệ (rất nguy hiểm cho người lập mã) này bị phá vỡ khi kết quả của phép nhân này được đưa vào phép nhân khác, với một phần tử đơn vị khác.

Cập nhật ngày 2012-01-27. Xin nói thêm một chút về các phần bù. Một phần bù của x thường được định nghĩa bằng cách lấy một hằng số c cố định, có í nghĩa đặc biệt nào đó, trừ đi x. Trong số học của phép cộng và phép nhân thông thường, ta có thể chọn hằng số c đó là 0, để phần bù của x chính là 0 – x = -x.

Vậy cái “í nghĩa đặc biệt” ấy của 0 là gì? 0 – x thì có gì “đặc biệt” hơn là 2012 – x hay 3.14 – x? Sự đặc biệt nằm ở chỗ, phần bù luôn có hai cách tính. Bên cạnh cách tính bằng phép trừ như trên, ta còn có thể tính phần bù của x bằng cách lấy x nhân với một hằng số i cố định. Ở đây, hằng số i ấy là -1:

x \ast (-1) = -x

Để í rằng phép tính phần bù có tính đối hợp nên số i như thế muốn dùng được cũng phải có tính đối hợp (nghĩa là nó khác đơn vị nhưng cũng như đơn vị, nó là nghịch đảo của chính mình):

(-1) \ast (-1) = 1

Và cái “í nghĩa đặc biệt” của c được suy từ tính chất đặc biệt này của i:

x + x \ast i = c

Đối với các phép nhân “đặc biệt” \odot và \otimes đã được giới thiệu, với đơn vị e đã chọn trước, số i thỏa yêu cầu là i = e – 1:

(e-1) \odot (e-1) = e

Và số c tương ứng là 2e – 1 cho \odot, và 1 – 2e cho \otimes:

x \odot (e-1) = 2e – 1 – x

x \otimes (e-1) = 1 – 2e – x

Chính vì thế mà “bội” của phần bù bằng phần bù của “bội”:

(2e – 1 – x) \odot y = 2e – 1 – (x \odot y)

(1 – 2e – x) \otimes y = 1 – 2e – (x \otimes y)

Như thế, phần bù nào cũng đều có “tính số học” cả. Phần bù luận lí của x, ngoài định nghĩa “luận lí” \neg x = (-1) \oplus x còn có thể được định nghĩa một cách rất chi là “số học”:

\neg x = -1 – x

Để thấy phần bù luận lí hoàn toàn nằm trong khuôn khổ của định nghĩa tổng quát về phần bù nói trên, ta hãy xem lại một lần nữa, các hệ thức trên ở dạng đặc biệt cho e = 0:

(-1) \cdot (-1) = 0

x \cdot (-1) = \neg x

x \times (-1) = 1 – x

(\neg x) \cdot y = \neg(x \cdot y)

(1 – x) \times y = 1 – (x \times y)

và cho e = 1:

0 \odot 0 = 1

x \odot 0 = 1 – x

x \otimes 0 = \neg x

(1 – x) \odot y = 1 – (x \odot y)

(\neg x) \otimes y = \neg (x \otimes y)

Ta cũng thấy rõ rằng, nói cho cùng, phần bù cho dù đã được xây dựng một cách thuần túy số học như ta đã làm vẫn hoàn toàn có thể có “tính luận lí” rất rõ ràng trong lựa chọn đơn vị cụ thể nào đó, như e = 0 và e = 1. Và “tính luận lí” này rất nguy hiểm. Chúng được gọi là phần bù luận lí chính bởi vì chúng tương thích với phép toán bit như xor và quay.

Chỉ có đa dạng hóa phép nhân mới giúp chế ngự được tính chất nguy hiểm này.

(còn tiếp)

Ada

(tiếp theo)

Thuật toán hoàn chỉnh. Đoạn này nêu những sửa đổi thuật toán sơ khai để thuật toán trở thành hoàn chỉnh.

Ngoài cụm rõ (X) và cụm mã (Y) có độ dài 4w bit, khóa (Z) 5w bit, ta dùng thêm một nắn T dài 4w bit và một khóa đơn vị U dài w bit.

Hàm G được cải biên, thay cho hai phép \times ta dùng hai phép \otimes với đơn vị khác nhau, evà e’. Và giữa hai nửa của G, một từ nắn (t) được trộn vào văn bản:

G(x, z, z’, e, e’, t) = (((x \otimes z)\mathrm{^S} \oplus t) \otimes z’)\mathrm{^S}

Để khởi động thuật toán mã hóa, nắn T được chia thành 4 đoạn dài w bit và nạp vào 4 thanh ghi t_0, t_1, t_2, t_3 (gọi là các thanh ghi nắn) theo thứ tự từ thấp đến cao:

(t_0,t_1,t_2,t_3) \leftarrow T

Và khóa đơn vị U được nạp, dưới dạng số đối, vào một thanh ghi u (gọi là thanh ghi đơn vị):

u \leftarrow -U

Trong mỗi vòng, giống như thanh ghi khóa z_{3}, thanh ghi đơn vị u cũng được đọc ra hai lần. Hai lần đó cho hai giá trị khác nhau u, u’ bởi vì thanh ghi đơn vị cứ sau mỗi lần đọc ra lại được cập nhật bằng cách tự cộng thêm 2*U+1:

u\leftarrow u+2\ast U+1

Hai từ khóa z_{3}, z_{3}’ và hai từ đơn vị u, u’ trong mỗi vòng đi vào hai vòng (con) của hàm G, từ nắn t_{0} đi vào giữa hai vòng (con) của G, tất cả đều lần lượt cập nhật thanh ghi x_{0}:

x_0 \leftarrow G(x_0, z_3, z_3′, u, u’, t_0)

Sau mỗi vòng, tương tự như các thanh ghi văn bản và các thanh ghi khóa, các thanh ghi nắn cũng được hoán vị vòng quanh:

(t_0,t_1,t_2,t_3) \leftarrow (t_1,t_2,t_3,t_0)

Để tổng hợp, ta viết lại bằng ngôn ngữ C++ toàn bộ thuật toán mã hóa hoàn chỉnh trên các từ 32 bit:

typedef uint32_t word;
// nếu trình biên dịch không biết kiểu uint32_t thì
// có thể thử unsigned __int32 hoặc unsigned int

static inline word o(word a, word b, word e) // toán tử (x) với đơn vị e
{
return 2*a*b + (1 – 2*e)*(a – b + e);
}

static inline word G(word x, word z0, word z1, word u0, word u1, word t)
{
x = o(x,z0,u0);
x = _rotl(x,16);
x ^= t;
x = o(x,z1,u1);
x = _rotl(x,16);
return x;
}

void encrypt( word Y[4], word const X[4], word const Z[5], word const T[4], word U )
{
word
x0 = X[0], x1 = X[1], x2 = X[2], x3 = X[3],
z0 = Z[0], z1 = Z[1], z2 = Z[2], z3 = Z[3], z4 = Z[4],
t0 = T[0], t1 = T[1], t2 = T[2], t3 = T[3],
u0 = -U,
u1 = u0 + 2*U + 1;

for(int k = 0; k < 32; k++)
{
// 8 <= k < 16 or 24 <= k < 32 iff bit3(k) == 1
if(k & 8) // vòng thuộc loại B
{
x3 ^= x0;
x0 = G(x0, z3, z4, u0, u1, t0);
}
else // vòng thuộc loại A
{
x0 = G(x0, z3, z4, u0, u1, t0);
x1 ^= x0;
}
word x = x0; x0 = x1; x1 = x2; x2 = x3; x3 = x;
word z = z0; z0 = z2; z2 = z4; z4 = z1; z1 = z3; z3 = z;
word t = t0; t0 = t1; t1 = t2; t2 = t3; t3 = t;
u0 = u1 + 2*U + 1;
u1 = u0 + 2*U + 1;
}
Y[0] = x0; Y[1] = x1; Y[2] = x2; Y[3] = x3;
}

Nắn T được sinh ra từ số thứ tự của cụm và một khóa 4w bit, gọi là khóa nắn, theo cách tương tự như các đơn vị được sinh ra từ số thứ tự vòng và khóa đơn vị. Cụ thể như sau.

Gọi T^{(j)} là nắn dùng để mã hóa cụm thứ j. Đối với cụm đầu tiên (j=0), giá trị khóa nắn được dùng luôn làm nắn:

T^{(0)} = khóa nắn

Nắn cho cụm sau được tính từ nắn của cụm trước, theo công thức truy hồi:

T^{(j+1)} = T^{(j)} + 2 \ast T^{(0)} + 1

Hoặc, nếu cần truy nhập ngẫu nhiên đến cụm thứ j, ta có thể tính trực tiếp:

T^{(j)} = T^{(0)} \cdot j

Trong các hệ thức trên, mọi phép tính đều được thực hiện mod 2^{4w}, nói cách khác ta coi mọi toán hạng kể cả các hằng số 1 và 2 đều là những số có độ dài 4w bit. Số học 4w bit có thể thực hiện được bằng ngôn ngữ C, nhưng sẽ đạt hiệu quả cao hơn rất nhiều khi thực hiện bằng hợp ngữ. Có thể tham khảo mã nguồn, chẳng hạn, tại http://locklessinc.com/articles/256bit_arithmetic.

Công thức truy hồi hiệu quả hơn hẳn so với công thức trực tiếp. Khi thực hiện bằng hợp ngữ, nó chỉ mất 4 phép cộng từ đơn có carry, nghĩa là 4 xung nhịp của bộ vi xử lí. Vậy nên trong thực tiễn truy nhập ngẫu nhiên, ta vẫn nên áp dụng nó bất cứ khi nào có thể. Chẳng hạn, để mã hóa hay giải mã một sector trên ổ đĩa cứng (nơi mọi sector đều được mã hóa bằng cùng một khóa và các cụm dữ liệu được đánh số thứ tự từ đầu đến cuối ổ đĩa, hơn là từ đầu đến cuối sector), ta chỉ dùng công thức trực tiếp để tính nắn cho cụm dữ liệu đầu tiên của sector, còn các cụm kế tiếp thì dùng công thức truy hồi.

Việc có nắn hay không còn tùy theo mục đích và cách thức sử dụng mật mã. Để mã hóa một cách trực tiếp, như đã nói trước đây, việc nắn là tuyệt đối cần thiết. Để sinh một loạt số giả ngẫu nhiên độc lập với nhau ta có thể nắn hay không nắn, và nếu nắn thì sẽ tốt hơn vì dãy số sinh ra sẽ tuần hoàn với chu kì dài hơn nhiều (dài đến mức có thể xem là vô tận, không bao giờ lặp lại). Nhưng để sinh ra một loạt số giả ngẫu nhiên đôi một khác nhau thì ta không được phép nắn, nghĩa là xem T như một khóa bình thường, luôn giữ một giá trị nào đó không đổi trong suốt thời gian sinh loạt số.

(còn tiếp)

Ada

(tiếp theo)

Mã nguồn trong đoạn trên là một cách thực hiện chuẩn mực, nhưng không phải là cách thực hiện nhanh nhất của thuật toán này. Chẳng hạn, ta thấy trong đó:

— Phép toán \otimes mất 8 phép tính (2 phép cộng, 2 phép trừ, 2 phép nhân, và 2 phép nhân với 2).

— Hàm G mất 19 phép tính (2 phép \otimes, 2 phép S và 1 phép xor).

— Mỗi vòng mất 40 phép tính (19 phép tính trong hàm G, 1 phép xor, 2 phép cộng cho thanh ghi đơn vị (u_0,u_1), và 16 phép gán để thực hiện các hoán vị vòng quanh, 1 phép “&” và 1 phép “++” trên chỉ số k, đó là còn chưa kể đến 2 phép nhảy có điều kiện trong các cấu trúc điều khiển for và if).

— Hàm encrypt() mất 40*32 = 1280 phép tính. Như vậy ta mất khoảng 1280 xung nhịp để mã hóa một cụm trên một bộ vi xử lí hiện đại. (Thực ra, ước tính này là rất thô sơ. Trên một bộ vi xử lí hiện đại, một phép nhân vẫn mất vài xung nhịp, nhưng bù lại bộ vi xử lí có thể làm song song vài phép tính nếu những phép tính đó không lệ thuộc lẫn nhau.)

Những đoạn sau sẽ chỉ ra các phương thức tối ưu hóa, mà kết hợp lại sẽ giảm thời gian thực hiện xuống còn khoảng 256 xung nhịp, tức là nhanh hơn thực hiện chuẩn mực gấp 5 lần.

(còn tiếp)

Ada

(tiếp theo)

Hướng dẫn thực hiện. Trong lập trình, một nguyên tắc tối ưu hóa mã nguồn sơ đẳng là kĩ thuật tính sẵn (precomputation): trước khi vào một vòng lặp, hãy tính sẵn mọi giá trị cần thiết ở bên ngoài vòng lặp. Lập trình mật mã cũng vậy thôi. Ta hãy xem lưu đồ dữ liệu.

2*U+1 t3(0) t1(0) x3(0) x1(0) z4(0) z2(0) z0(0)
| u(0) | t2(0) | t0(0) | x2(0) | x0(0) | z3(0) | z1(0) |
| | | | | | | | | | | | | | |
| | | | | | | | | +-+-+ | | | | |
| o———————————->|] <|<-------o | | |
| | | | | | | | | | | | | | | |
o–>[+] | | | | | | | | | \ \ \ \ |
| | | | | o—————>+ G | +-\—\—\—\-+
| u(1) | | | | | | | | | | \ \ \ \
| | | | | | | | | | | | z3(1) | z1(1) |
| o———————————->|] <|<-------o z2(1) | z0(1)
| | | | | | | | | +-+-+ | | | | |
o–>[+] | | | | | | | | z4(1) | | | |
| | | | | | | | +<--o | | | | |
| | | | | | | | | | | | | | |
| | \ \ \ | \ \ \ | \ \ \ \ |
| | +-\—\—\-+ +-\—\—\-+ +-\—\—\—\-+
| | | \ \ \ | \ \ \ | \ \ \ \
| | | | | | | | | | | | | | |
| u(2) | t2(1) | t0(1) | x2(1) | x0(1) | z3(2) | z1(2) |
2*U+1 t3(1) t1(1) x3(1) x1(1) z4(2) z2(2) z0(2)

Hình 1A. Vòng 0 của thuật toán mã hóa.

2*U+1 t3(8) t1(8) x3(8) x1(8) z4(16) z2(16) z0(16)
| u(16) | t2(8) | t0(8) | x2(8) | x0(8) | z3(16)| z1(16)|
| | | | | | | | | | | | | | |
| | | | | | +<----------o | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | +-+-+ | | | | |
| o———————————->|] <|<-------o | | |
| | | | | | | | | | | | | | | |
o–>[+] | | | | | | | | | \ \ \ \ |
| | | | | o—————>+ G | +-\—\—\—\-+
| u(17) | | | | | | | | | | \ \ \ \
| | | | | | | | | | | | z3(17)| z1(17)|
| o———————————->|] <|<-------o z2(17)|z0(17)
| | | | | | | | | +-+-+ | | | | |
o–>[+] | | | | | | | | z4(17)| | | |
| | \ \ \ | \ \ \ | \ \ \ \ |
| | +-\—\—\-+ +-\—\—\-+ +-\—\—\—\-+
| | | \ \ \ | \ \ \ | \ \ \ \
| | | | | | | | | | | | | | |
| u(18) | t2(9) | t0(9) | x2(9) | x0(9) | z3(18)| z1(18)|
2*U+1 t3(9) t1(9) x3(9) x1(9) z4(18) z2(18) z0(18)

Hình 1B. Vòng 8 của thuật toán mã hóa.

Cần tưởng tượng rằng hàm ENCRYPT được nằm trong một vòng lặp lớn: với một bộ khóa (Z, T, U) nhất định, ENCRYPT sẽ được gọi nhiều lần để mã hóa nhiều cụm rõ. Vậy thực chất những thứ có thể tính sẵn trước là những thông tin không lệ thuộc vào giá trị của cụm rõ mà chỉ lệ thuộc vào bộ khóa, cụ thể là (i) dãy các giá trị của thanh ghi z_3 và z_4 trong từng vòng, (ii) dãy các giá trị của thanh ghi u_0 và u_1 trong từng vòng, và (iii) dãy các giá trị của thanh ghi t_0 trong từng vòng.

Đối với (i), ta tính sẵn dãy này trong một mảng K gồm 64 từ:

K = (Z_3, Z_4, Z_0, Z_1, Z_2, Z_3, Z_4, Z_0, Z_1, Z_2, …, Z_3, Z_4, Z_0, Z_1, Z_2, Z_3, Z_4, Z_0, Z_1)

trong đó Z_4 Z_3 Z_2 Z_1 Z_0 = Z

Đối với (ii), ta tính sẵn dãy này trong một mảng L gồm 64 từ:

L = (-U, U+1, 3U+2, 5U+3, …, 125U+63)

Đối với (iii), ta tính sẵn dãy này trong một mảng C gồm 32 từ:

C = (T_0, T_1, T_2, T_3, T_0, T_1, T_2, T_3, …, T_0, T_1, T_2, T_3)

trong đó T_3 T_2 T_1 T_0 = T

Sau đó, ta loại bỏ các thanh ghi khóa, các thanh ghi nắn và cặp thanh ghi đơn vị cũng như các phép gán chúng để hoán vị vòng quanh và các phép cộng cập nhật chúng ra khỏi mã nguồn của ENCRYPT, ta được một phiên bản mới nhẹ hơn, gọi là CRYPT. Để mã hóa cụm X thành cụm Y, thay vì dùng

Y \leftarrow \mathrm{ENCRYPT}(X, Z, T, U)

ta sẽ dùng:

Y \leftarrow \mathrm{CRYPT}(X, K, C, L)

Trong đoạn này và các đoạn tiếp theo, tên hàm (toán học) được viết hoa để phân biệt với hàm của ngôn ngữ C. Chẳng hạn, ENCRYPT là một hàm toán học, còn encrypt là một hàm C thực hiện hàm toán học ấy.

Các mảng K, C, L được gọi là các thời biểu khóa (key schedule) hoặc khóa bung (expanded key), còn bản thân việc lập ra chúng gọi là lập thời biểu khóa (key scheduling) hoặc bung khóa (key expansion). Các hàm bung khóa tương ứng sẽ được kí hiệu lần lượt là KE, TE và UE, vậy

K = \mathrm{KE}(Z)

L = \mathrm{UE}(U)

C = \mathrm{TE}(T)

(còn tiếp)

Ada

(tiếp theo)

Có một điều lí thú là thực hiện theo cách trên, CRYPT không những dùng để mã hóa mà còn có thể dùng để giải mã! Tính tương tự giữa mã hóa và giải mã không những có ích cho việc lập trình hiệu quả mà còn là rất thiết yếu để đảm bảo rằng việc tấn công vào mật mã theo hướng nào, bất kể là từ bản rõ đến bản mã, từ bản mã đến bản rõ, hay là từ bản rõ và bản mã vào giữa, cũng đều khó khăn như nhau.

Để cảm nhận sự thật này, trước hết hãy xem lưu đồ dữ liệu của thuật toán ở dạng đầy đủ, thu được từ việc ghép nối tiếp 32 lưu đồ vòng loại A (Hình 1A) và loại B (Hình 1B) sau đó “tháo xoắn”, nghĩa là loại bỏ các hoán vị vòng quanh.

X3 X2 X1 X0
| | | |
| | | 0 G<-Z3,Z4,T0
| | +<---------o
| | 1 G<-Z0,Z1,T1|
| +<---------o |
| 2 G<-Z2,Z3,T2| |
+<---------o | |
3 G<-Z4,Z0,T3| | |
o——————————->+
| | | 4 G<-Z1,Z2,T0
| | +<---------o
| | 5 G<-Z3,Z4,T1|
| +<---------o |
| 6 G<-Z0,Z1,T2| |
+<---------o | |
7 G<-Z2,Z3,T3| | |
| —————————-o
| / | | |
o–/—————————->+
/ | | 8 G<-Z4,Z0,T0
/ | o———>+
+ | 9 G<-Z1,Z2,T1|
| o———>+ |
| 10 G<-Z3,Z4,T2| |
o———>+ | |
11 G<-Z0,Z1,T3| | |
+<-------------------------------o
| | | 12 G<-Z2,Z3,T0
| | o———>+
| | 13 G<-Z4,Z0,T1|
| o———>+ |
| 14 G<-Z1,Z2,T2| |
o———>+ | |
15 G<-Z3,Z4,T3| | |
| | | |
| | | 16 G<-Z0,Z1,T0
| | +<---------o
| | 17 G<-Z2,Z3,T1|
| +<---------o |
| 18 G<-Z4,Z0,T2| |
+<---------o | |
19 G<-Z1,Z2,T3| | |
o——————————->+
| | | 20 G<-Z3,Z4,T0
| | +<---------o
| | 21 G<-Z0,Z1,T1|
| +<---------o |
| 22 G<-Z2,Z3,T2| |
+<---------o | |
23 G<-Z4,Z0,T3| | |
| —————————-o
| / | | |
o–/—————————->+
/ | | 24 G<-Z1,Z2,T0
/ | o———>+
+ | 25 G<-Z3,Z4,T1|
| o———>+ |
| 26 G<-Z0,Z1,T2| |
o———>+ | |
27 G<-Z2,Z3,T3| | |
+<-------------------------------o
| | | 28 G<-Z4,Z0,T0
| | o———>+
| | 29 G<-Z1,Z2,T1|
| o———>+ |
| 30 G<-Z3,Z4,T2| |
o———>+ | |
31 G<-Z0,Z1,T3| | |
| | | |
Y3 Y2 Y1 Y0

Hình 2. Thuật toán mã hóa đầy đủ.

Sau đây, bên cạnh các toán tử đã định nghĩa trên một từ, ta sẽ dùng vài toán tử trên các toán hạng nhiều từ.

— Toán tử (.)\mathrm{^R} kí hiệu sự đảo ngược thứ tự từ của một số nhiều từ, và toán tử (.)\mathrm{^S} kí hiệu sự hoán đổi nửa thấp với nửa cao của từng từ. Ví dụ, với từ 8 bit (w=8),

\text{0x01234567^R} = \text{0x67452301}

\text{0x01234567^S} = \text{0x10325476}

\text{0x01234567^{RS}} = \text{0x76543210}

Hiển nhiên (.)\mathrm{^S} và (.)\mathrm{^R} đều có tính đối hợp: với mọi a ta luôn có a \mathrm{^S^S} = a và a \mathrm{^R^R} = a. Và cũng dễ thấy rằng (.)\mathrm{^S} và (.)\mathrm{^R} giao hoán, nghĩa là a \mathrm{^R ^S} = a \mathrm{^S ^R} với mọi a.

— Các toán tử +, -, -(.), (.)’, \frac{x}{y} và \frac{1}{x} kí hiệu áp dụng toán tử cùng tên định nghĩa cho từ lên từng từ tương ứng của các toán hạng. Ví dụ,

(a, b, c,…)’ = (a’, b’, c’,…)

-(a, b, c,…) = (-a, -b, -c,…)

\frac{1}{(a, b, c,…)} = (\frac{1}{a}, \frac{1}{b}, \frac{1}{c},…)

(a_1, b_1, c_1,…) + (a_2, b_2, c_2,…) = (a_1+a_2, b_1+b_2, c_1+c_2,…)

(a_1, b_1, c_1,…) – (a_2, b_2, c_2,…) = (a_1-a_2, b_1-b_2, c_1-c_2,…)

\frac{(a_1, b_1, c_1,…)}{(a_2, b_2, c_2,…)} = (\frac{a_1}{a_2}, \frac{b_1}{b_2}, \frac{c_1}{c_2},…)

Từ lưu đồ dữ liệu, dễ dàng suy được qui trình giải mã dùng CRYPT như sau.

1. Đem cụm mã Y đảo ngược thứ tự các từ và hoán đổi nửa thấp với nửa cao của từng từ, được Y*:

Y* \leftarrow Y \mathrm{^R^S}

2. Đem nắn T đảo ngược thứ tự các từ và hoán đổi nửa thấp với nửa cao của từng từ, xem kết quả thu được như một nắn mới, đem bung nó ra, được C*:

C* \leftarrow \mathrm{TE}(T \mathrm{^R^S})

3. Bung khóa đơn vị U, rồi đem kết quả thu được đảo ngược thứ tự các từ, được L*:

L* \leftarrow \mathrm{UE}(U) \mathrm{^R}

4. Đảo ngược thứ tự các từ của khóa Z rồi bung nó ra, kết quả thu được đem lấy nghịch đảo của từng từ theo phép nhân \odot với đơn vị là từ tương ứng của L*, ta được K*:

K* \leftarrow (\mathrm{KE}(Z \mathrm{^R}) – L*)’ + L*

5. Dùng CRYPT, mã hóa Y* với các khóa bung K*, C* và L*, được X*:

X* \leftarrow \mathrm{CRYPT}(Y*, K*, C*, L*)

6. Đảo ngược thứ tự các từ của X* và hoán đổi nửa thấp với nửa cao của từng từ, sẽ khôi phục được cụm rõ X ban đầu:

X \leftarrow X* \mathrm{^R^S}

Để tóm tắt, ta nêu lại các hệ thức giữa hàm ENCRYPT, DECRYPT và CRYPT:

\mathrm{DECRYPT}( \mathrm{ENCRYPT}(X,Z,T,U),Z,T,U) = X

\mathrm{CRYPT}( \mathrm{CRYPT}(X,\mathrm{KE}(Z),\mathrm{TE}(T), \mathrm{UE}(U)) \mathrm{^R^S}, (\mathrm{KE}(Z \mathrm{^R})-\mathrm{UE}(U)\mathrm{^R})’+\mathrm{UE}(U) \mathrm{^R}, \mathrm{TE}(T \mathrm{^R^S}), \mathrm{UE}(U) \mathrm{^R} ) \mathrm{^R^S} = X

\mathrm{ENCRYPT}(X,Z,T,U) = \mathrm{CRYPT}(X, \mathrm{KE}(Z), \mathrm{TE}(T), \mathrm{UE}(U))

\mathrm{DECRYPT}(Y,Z,T,U) = \mathrm{CRYPT} (Y \mathrm{^R^S}, (\mathrm{KE} (Z \mathrm{^R} ) – \mathrm{UE} (U) \mathrm{^R})’+\mathrm{UE} (U) \mathrm{^R}, \mathrm{TE} (T \mathrm{^R^S}), \mathrm{UE} (U) \mathrm{^R} ) \mathrm{^R^S}

Trong đó X, Y, Z, T, U là những giá trị bất kì với độ dài lần lượt 4w, 4w, 5w, 4w, w bit. Hệ thức thứ nhất chỉ đơn giản giới thiệu rằng ENCRYPT (mã hóa) và DECRYPT (giải mã) là hai hàm “ngược” của nhau. Hệ thức thứ ba và thứ tư cho phương pháp tính 2 hàm này.

(còn tiếp)

Ada

(tiếp theo)

Ta đã biết rằng phép toán \otimes dùng trong thuật toán thực chất chỉ đem đến độ phức tạp ngang với một phép nhân thông thường cùng với 1 phép đổi dấu trước và sau phép nhân. Nhưng trong mã nguồn, \otimes tốn mất 8 phép tính. Như vậy cân nhắc hiệu quả và chi phí thì chúng ta đang bị “lỗ” to!

May thay, thực tế không phải là như thế. Khi mã hóa nhiều cụm văn bản, phần lớn các phép tính đều có thể tính sẵn trước khi biết giá trị của cụm văn bản, sao cho toán tử \otimes với văn bản thật sự có thể thực hiện được chỉ bằng 1 phép nhân và 1 phép cộng:

x \otimes z = x \ast m + n

Trong đó x là một từ văn bản, z là một từ của khóa, phép toán \otimes được định nghĩa với một đơn vị u cố định nào đó, và

m = 2(z – u) + 1

n = (2u – 1) \ast (z – u)

Để mã hóa, ta có thể tính sẵn 64 từ m và 64 từ n tương ứng cho 64 toán tử \otimes, lưu chúng trong các mảng M và N, và dùng 2 mảng này thay cho mảng K và L khi mã hóa. Chi phí bộ nhớ không thay đổi, nhưng chi phí tính toán thì giảm hẳn.

Để giải mã, chỉ cần để ý rằng

(x \ast m + n) \ast \frac{1}{m} – \frac{n}{m} = x

Vậy, cũng như hàm CRYPT ở đoạn trên, hàm CRYPT (mới) ở đây cũng có thể dùng để giải mã, bằng thời biểu khóa lập sẵn với \frac{1}{m} thế chỗ cho m và – \frac{n}{m} thế chỗ cho n. Lưu ý một lần nữa là toán tử \frac{x}{y} kí hiệu phép nhân với nghịch đảo của mẫu số (vốn dĩ luôn là một số lẻ) modulo 2^w.

Gọi ME và NE là các hàm bung khóa (sao cho M = \mathrm{ME}(Z,U), N = \mathrm{NE}(Z,U)), ta có thể tóm tắt lại cách dùng phiên bản mới của CRYPT để mã hóa và giải mã như sau:

\mathrm{CRYPT}( \mathrm{CRYPT}(X,T,\mathrm{ME}(Z,U),\mathrm{NE}(Z, U))\mathrm{^R^S},T \mathrm{^R^S}, \frac{1} { \mathrm{ME}(Z,U) \mathrm{^R} }, – \frac{ \mathrm{NE}(Z,U) \mathrm{^R} } { \mathrm{ME} (Z,U) \mathrm{^R} } ) \mathrm{^R^S} = X

\mathrm{ENCRYPT}(X,Z,T,U) = \mathrm{CRYPT}(X,T, \mathrm{ME}(Z,U), \mathrm{NE}(Z,U))

\mathrm{DECRYPT}(Y,Z,T,U) = \mathrm{CRYPT}( Y \mathrm{^R^S}, T \mathrm{^R^S}, \frac{1}{ \mathrm{ME} (Z,U) \mathrm{^R} }, – \frac{ \mathrm{NE} (Z,U) \mathrm{^R} } { \mathrm{ME} (Z,U) \mathrm{^R} } ) \mathrm{^R^S}

(còn tiếp)

Ada

(tiếp theo)

Khi thực hiện các thuật toán nói chung và mã hóa nói riêng, một kĩ thuật quan trọng mà chúng ta không thể bỏ qua là khai thác khả năng tính toán song song của bộ vi xử lí. Thuật toán mật mã giới thiệu ở đây hiển nhiên là cho phép dùng nhiều lõi (core) của bộ vi xử lí để mã hóa song song nhiều cụm. Nhưng liệu trong phạm vi 1 cụm, nó có cho phép thực hiện các phép tính song song bằng các đơn vị thi hành (execution unit) của 1 lõi hay không?

Để trả lời câu hỏi này, cách trực quan nhất là ta hãy xem lưu đồ dữ liệu. Lưu đồ vẽ trên Hình 2 là lưu đồ đã được “tháo xoắn”, tức là đã lược đi tất cả các hoán vị vòng quanh để cho các luồng dữ liệu quan trọng được “duỗi thẳng” ra. Nhưng trong lưu đồ đó vẫn còn tiềm ẩn những luồng dữ liệu “xoắn” khác nữa mà để thấy rõ chúng, cần phải “tháo xoắn” ở một cấp độ cao hơn nữa (xem Hình 3).

1 4 7 10 13 16 19 22 25 28 31
G G G G G G G G G G G
|\ |\ | \ \ |\ |\ |\ \ \ \
| \ | \ | \ \ | \ | \ | \ \ \ \
X2 | \ | o—–o—–+—–+ | \ | \ | o—–+—–+ Y3
\ | \ | \ | \ \ \ | \ | \ | \ \ \
\|2 \|5 \|8 \ 11 \ 14 \|17 \|20 \|23 \ 26 \ 29 \
G G G G G G G G G G Y0
|\ |\ \ \ \ |\ |\ | \ \
| \ | \ \ \ \ | \ | \ | \ \
X0 X3 | \ | o—–+—–+—–+ | \ | o—–o—–+—–+
\ \ | \ | \ \ \ \ | \ | \ | \ \ \
\ 0 \|3 \|6 \ 9 \ 12 \ 15 \|18 \|21 \|24 \ 27 \ 30 \
G G G G G G G G G G G Y1
|\ |\ |\ \ \ \ |\ |\ \ \ \
| \ | \ | \ \ \ \ | \ | \ \ \ \
X1| \ | \ | o—–+—–+ \ | \ | o—–+—–+—–+
\ | \ | \ | \ \ \ \ | \ | \ \ \ \
\|1 \|4 \|7 \ 10 \ 13 \ 16 \|19 \|22 \ 25 \ 28 \ 31 \
G G G G G G G G G G G Y2

Hình 3. Thuật toán mã hóa đầy đủ,
thu được bằng cách “tháo xoắn” Hình 2.

(còn tiếp)

Ada

(tiếp theo)

Lưu đồ dữ liệu ở Hình 3 cho một cái nhìn xuyên thấu hơn vào thuật toán, nhờ đó giúp dễ dàng cảm nhận được một số tính chất của thuật toán từ quan điểm phân tích mật mã. Ví dụ, nó có thể giúp ta lí giải được tại sao khóa Z lại có 5 từ mà không phải là 4 từ hay 6 từ. Nhưng ở đây, ta sẽ không quan tâm đến những tính chất như thế mà chỉ quan tâm đến khía cạnh thực thi, mà cụ thể là tính toán song song. Gọi g^{(k)} là kết quả của hàm G ở vòng k, từ lưu đồ dữ liệu, dễ dàng suy ra được một qui trình thực hiện gồm 20 bước nối tiếp, như sau.

1. Tính g^{(0)}
2. Tính g^{(1)}
3. Tính g^{(2)}
4. Tính g^{(3)}
5. Tính g^{(4)}
6. Tính g^{(5)}, g^{(11)} song song
7. Tính g^{(6)}, g^{(9)} song song
8. Tính g^{(7)}, g^{(10)}, g^{(13)} song song
9. Tính g^{(8)}, g^{(14)} song song
10. Tính g^{(12)}, g^{(15)} song song
11. Tính g^{(16)}
12. Tính g^{(17)}
13. Tính g^{(18)}
14. Tính g^{(19)}
15. Tính g^{(20)}
16. Tính g^{(21)}, g^{(27)} song song
17. Tính g^{(22)}, g^{(25)} song song
18. Tính g^{(23)}, g^{(26)}, g^{(29)} song song
19. Tính g^{(24)}, g^{(30)} song song
20. Tính g^{(28)}, g^{(31)} song song

Ta kết hợp lại tất cả các kĩ thuật tối ưu hóa đã nêu bằng một mã nguồn C++ mới, viết cho trường hợp độ dài từ 32 bit.

void expandkey (word M[64], word N[64], word const Z[5], word U)
{
word z0=Z[0], z1=Z[1], z2=Z[2], z3=Z[3], z4=Z[4];
word u = -U;
for( int k=0; k<64; k++ )
{
M[k] = 2*(z3 – u) + 1;
N[k] = (2*u – 1)*(z3 – u);
u += 2*U + 1;
word z=z0; z0=z1; z1=z2; z2=z3; z3=z4; z4=z;
}
}

static inline word G (word x, word t, word m0, word m1, word n0, word n1)
{
x *= m0;
x += n0;
x = _rotl(x,16);
x ^= t;
x *= m1;
x += n1;
x = _rotl(x,16);
return x;
}

void crypt(word Y[4], word const X[4], word const T[4], word const M[64], word const N[64])
{
// Step 1
word const g0 = G( X[0], T[0], M[0], M[1], N[0], N[1] );

// Step 2
word const g1 = G( X[1]^g0, T[1], M[2], M[3], N[2], N[3] );

// Step 3
word const g2 = G( X[2]^g1, T[2], M[4], M[5], N[4], N[5] );

// Step 4
word const g3 = G( X[3]^g2, T[3], M[6], M[7], N[6], N[7] );

// Step 5
word const g4 = G( g0^g3, T[0], M[8], M[9], N[8], N[9] );

// Step 6
word const g5 = G( g1^g4, T[1], M[10],M[11],N[10],N[11] );
word const g11= G( g4, T[3], M[22],M[23],N[22],N[23] );

// Step 7
word const g6 = G( g2^g5, T[2], M[12],M[13],N[12],N[13] );
word const g9 = G( g5, T[1], M[18],M[19],N[18],N[19] );

// Step 8
word const g7 = G( g3^g6, T[3], M[14],M[15],N[14],N[15] );
word const g10= G( g6, T[2], M[20],M[21],N[20],N[21] );
word const g13= G( g6^g9, T[1], M[26],M[27],N[26],N[27] );

// Step 9
word const g8 = G( g4^g7, T[0], M[16],M[17],N[16],N[17] );
word const g14= G( g4^g10, T[2], M[28],M[29],N[28],N[29] );

// Step 10
word const g12= G( g5^g8, T[0], M[24],M[25],N[24],N[25] );
word const g15= G( g5^g8^g11, T[3], M[30],M[31],N[30],N[31] );

// Step 11
word const g16= G( g6^g9^g12, T[0], M[32],M[33],N[32],N[33] );

// Step 12
word const g17= G( g4^g10^g13^g16, T[1], M[34],M[35],N[34],N[35] );

// Step 13
word const g18= G( g5^g8^g11^g14^g17, T[2], M[36],M[37],N[36],N[37] );

// Step 14
word const g19= G( g15^g18, T[3], M[38],M[39],N[38],N[39] );

// Step 15
word const g20= G( g16^g19, T[0], M[40],M[41],N[40],N[41] );

// Step 16
word const g21= G( g17^g20, T[1], M[42],M[43],N[42],N[43] );
word const g27= G( g20, T[3], M[54],M[55],N[54],N[55] );

// Step 17
word const g22= G( g18^g21, T[2], M[44],M[45],N[44],N[45] );
word const g25= G( g21, T[1], M[50],M[51],N[50],N[51] );

// Step 18
word const g23= G( g19^g22, T[3], M[46],M[47],N[46],N[47] );
word const g26= G( g22, T[2], M[52],M[53],N[52],N[53] );
word const g29= G( g22^g25, T[1], M[58],M[59],N[58],N[59] );

// Step 19
word const g24= G( g20^g23, T[0], M[48],M[49],N[48],N[49] );
word const g30= G( g20^g26, T[2], M[60],M[61],N[60],N[61] );
Y[1] = g20^g26^g29;

// Step 20
word const g28= G( g21^g24, T[0], M[56],M[57],N[56],N[57] );
word const g31= G( g21^g24^g27, T[3], M[62],M[63],N[62],N[63] );
Y[2] = g21^g24^g27^g30;

// Step 21
Y[0] = g22^g25^g28;
Y[3] = g31;
}

Trên một bộ vi xử lí x86_64, khi dịch ở chế độ 32 bit, mã nguồn trên mất khoảng 256 xung nhịp để mã hóa 1 cụm (16 byte), tức khoảng 16 xung nhịp để mã hóa 1 byte.

Khi chỉnh sửa lại một chút cho độ dài từ 64 bit và biên dịch ở chế độ 64 bit, với độ dài cụm tăng gấp đôi, tốc độ cũng sẽ tăng gấp đôi, tức còn khoảng 8 xung nhịp để mã hóa 1 byte. (Đây là ước lượng thô sơ. Thực tế, các bộ vi xử lí như AMD K8 và Intel Core 2 có thể mất đến 10-12 xung nhịp bởi vì phép nhân 64 bit chậm hơn phép nhân 32 bit, phép nhân 64 bit trên Intel chậm hơn trên AMD.)

Ngoài ra, ta còn có thể ghép song song 2 đoạn mã nguồn trên (một cách khéo léo) để mã hóa đồng thời 2 cụm trên cùng một lõi của bộ vi xử lí, sẽ tiết kiệm được vài xung nhịp mỗi byte. Và cuối cùng, trên các bộ vi xử lý x86_64, ta còn có thể dùng các phép tính vector để mã hóa đồng thời 4 cụm trên cùng một lõi, tiết kiệm vài xung nhịp mỗi byte nữa.

Để so sánh, một cài đặt đã tối ưu hóa của thuật toán mật mã AES (với 14 vòng cho khóa 256 bit) thường mất khoảng 24 xung nhịp để mã hóa 1 byte.

Dưới đây là hàm sinh thời biểu khóa giải mã và hàm giải mã.

void invertkey( word iM[64], word iN[64], word const M[64], word const N[64] )
{
// M, N, iM, iN must not overlap!
for(int k=0; k < 64; k++)
{
iM[k] = inverse( M[63-k] );
iN[k] = – N[63-k] * iM[k];
}
}

void icrypt( word X[4], word const Y[4], word const T[4], word const iM[64], word const iN[64] )
{
word Xrs[4], Trs[4];
Trs[0] = _rotl(T[3],16);
Trs[1] = _rotl(T[2],16);
Trs[2] = _rotl(T[1],16);
Trs[3] = _rotl(T[0],16);
Xrs[0] = _rotl(Y[3],16);
Xrs[1] = _rotl(Y[2],16);
Xrs[2] = _rotl(Y[1],16);
Xrs[3] = _rotl(Y[0],16);
crypt( Xrs, Xrs, Trs, iM, iN );
X[0] = _rotl(Xrs[3],16);
X[1] = _rotl(Xrs[2],16);
X[2] = _rotl(Xrs[1],16);
X[3] = _rotl(Xrs[0],16);
}

Còn đây là chương trình thử, dùng để kiểm nghiệm rằng cài đặt đã tối ưu hóa:

— mã hóa chính xác, nghĩa là expandkey và crypt cho kết quả y hệt như hàm mã hóa chuẩn mực (encrypt), và

— giải mã chính xác, nghĩa là expandkey, invertkey và icrypt khôi phục lại cụm rõ đã được mã hóa bởi expandkey và crypt.

Chương trình thử cũng minh họa cách dùng các hàm để mã hóa và giải mã 1 cụm.

void test()
{
int const nTimes = 100;
int const nRep = 100;
word X[4], Y[4], T[4], Z[5], M[64], N[64], iM[64], iN[64];

for(int i=0; i<5; i++)
Z[i] = random_word();
for(int i=0; i<4; i++)
T[i] = random_word();
word U = random_word();

// correctness of the optimized implementation
expandkey( M, N, Z, U );
for(int n=nTimes; n; n–)
{
for(int i=0; i<4; i++)
X[i] = random_word();
memcpy( Y, X, sizeof(X) );
for(int m=nRep; m; m–)
{
encrypt ( X, X, Z, T, U );
crypt ( Y, Y, T, M, N );
}
if( memcmp(Y,X,sizeof(X)) !=0 )
cout << "crypt: mã hóa sai!" << endl;
}

// invertibility of the optimized implementation
invertkey( iM, iN, M, N );
for(int n=nTimes; n; n–)
{
for(int i=0; i<4; i++)
X[i] = random_word();
memcpy( Y, X, sizeof(X) );

for(int m=nRep; m; m–)
{
crypt( Y, Y, T, M, N );
}
for(int m=nRep; m; m–)
{
icrypt( Y, Y, T, iM,iN );
}
if( memcmp(Y, X, sizeof(X)) !=0 )
cout << "icrypt: giải mã sai!" << endl;
}
}

(còn tiếp)

Ada

(tiếp theo)

Vấn đề thực thi cuối cùng mà mình đề cập là phép tính nghịch đảo theo phép nhân modulo 2^w (modular multiplicative inverse) cần thiết để giải mã. Phép tính này có thời gian tính toán không phải là O(1) mà là O(w) nên mặc dù trong lí thuyết, phép tính này là dễ dàng nhưng trong thực hành thì vẫn còn được xem là phức tạp. Vì thế, khi lập trình, phép tính này không bao giờ được đưa vào hàm giải mã mà luôn luôn được đưa vào hàm bung khóa, nghĩa là các giá trị nghịch đảo để giải mã luôn luôn được tính sẵn.

Có hai cách tính.

Cách thứ nhất là dùng định lí Euler, là định lí nói rằng với mọi n nguyên dương và mọi a nguyên tố cùng nhau với n,

a^{\phi (n)} = 1 (mod n)

trong đó \phi (n) là số các số tự nhiên không lớn hơn n nguyên tố cùng nhau với n. Từ đó suy ra nghịch đảo của a là

\frac{1}{a} = a^{\phi (n)-1} (mod n)

Trong thuật toán mật mã này, n = 2^w, do vậy tập các số nguyên tố cùng nhau với n chính là tập các số tự nhiên lẻ, và ta có

\frac{1}{a} = a^{2^{w-1}-1} (mod 2^w)

Chẳng hạn, với các từ 8 bit (w=8) thì \frac{1}{a} = a^{127} = a \ast a \ast a \ast … \ast a (mod 256), với 126 phép nhân (của ngôn ngữ C trên kiểu unsigned char). Nhưng tất nhiên, khi lập trình, ta không làm nhiều phép nhân như thế, mà chỉ dùng 6 phép bình phương và 6 phép nhân thôi:

a^{127} = a^{126} \ast a
= (a^{63})^2 \ast a
= ((a^{31})^2 \ast a)^2 \ast a
= (((a^{15})^2 \ast a)^2 \ast a)^2 \ast a
= ((((a^7)^2 \ast a)^2 \ast a)^2 \ast a)^2 \ast a
= (((((a^3)^2 \ast a)^2 \ast a)^2 \ast a)^2 \ast a)^2 \ast a
= (((((a^2 \ast a)^2 \ast a)^2 \ast a)^2 \ast a)^2 \ast a)^2 \ast a

Mình cẩn thận nêu mã nguồn tính nghịch đảo của một từ 32 bit và, nhắc lại một lần nữa, từ ấy phải là một số lẻ.

word inverse(word a)
{
word b = a;
for(int w=30; w; w–)
{
b *= b;
b *= a;
}
return b;
}

Cách thứ hai là dùng thuật toán Euclid mở rộng, tức là thuật toán không những tính được ước chung lớn nhất (UCLN) của a và b mà còn tính được một nghiệm nguyên của phương trình

ax + by = \mathrm{UCLN}(a,b)

Áp dụng vào thuật toán mật mã này, a là số (lẻ) cần nghịch đảo, b = 2^w, (vậy \mathrm{UCLN}(a,b) = 1), ẩn số x là nghịch đảo của a trong phép nhân mod b, còn ẩn số y là nghịch đảo của b qua phép nhân mod a.

Các chi tiết của phương pháp này có thể được tìm thấy trong sách giáo khoa số học phổ thông.

Cách thứ hai thường nhanh hơn cách thứ nhất. Nhưng cách thứ nhất có thời gian tính toán hằng (nó luôn mất w-2 phép bình phương và w-2 phép nhân) còn cách thứ hai có thời gian tính toán lệ thuộc vào giá trị của a, nên xét về bảo mật thì cách thứ nhất an toàn hơn.

Trong ngữ cảnh của thuật toán mã hóa này, phép nghịch đảo chỉ được dùng khi bung khóa để giải mã, một việc chỉ tốn rất ít thời gian so với bản thân việc giải mã một bản mã gồm nhiều cụm. Khi dùng cách thứ hai, thời gian thực hiện từng bước của phép nghịch đảo cũng chỉ tiết lộ một ít thông tin về khóa mà thôi. Do vậy mà trên cả hai phương diện hiệu quả và bảo mật, lựa chọn cách nào là không quan trọng lắm.

Cập nhật ngày 2011-05-03. Sau khi đăng loạt bài này, mình được biết thêm cách thứ ba nữa. Cách này có thể xem như thuộc về Newton, người đã đưa ra thuật toán tính căn xấp xỉ. Mã nguồn và chứng minh ở phần này do Thomas Pornin giới thiệu trên Usenet năm 2009 (http://groups.google.com/group/sci.crypt/browse_thread/thread/2fd189dc6212ff29/7fd3bedbd0967d40?hl=en&ie=UTF-8&q=multiplicative+inverse+thomas+pornin).

Giả sử ta có a b = 1 (mod n) với những số nguyên a, b và n, nghĩa là

ab = 1 + u n

với số nguyên u nào đó. Ở đây a và b không nhất thiết phải dương hay nhỏ hơn n, nhưng dĩ nhiên b vẫn là một nghịch đảo của a modulo n. Với số nguyên v bất kì, đặt

b’ = b(2 – a b) + v n^2

ta có

a b’ = a b(2 – a b) + a v n^2
= (1 + u n)(1 – u n) + a v n^2
= 1 – u^2 n^2 + a v n^2
= 1 + (a v – u^2) n^2

Ta thấy ab’ = 1 (mod n^2), chứng tỏ rằng b’ là một nghịch đảo của a mod n^2.

Vậy, nghịch đảo modulo n^2 có thể tính được nhờ nghịch đảo modulo n và ta suy ra thuật toán tìm nghịch đảo của a (a lẻ) modulo 2^w, trong đó w là một lũy thừa của 2, như sau. Trước hết, hiển nhiên ta biết nghịch đảo của a mod 2: đó là số 1. Tiếp đó dùng công thức b’ ở trên, lần lượt tính nghịch đảo của a modulo 2^2 (công thức được đơn giản hóa thành b’ = 2 – a), 2^4, 2^8, 2^{16}, …, 2^w. Mọi phép tính đều có thể thực hiện modulo 2^w. Khi w=32, ta chỉ cần 8 phép nhân:

word inverse(word a)
{
word b = 2 – a; // a*b = 1 mod 4
b *= 2 – a*b; // a*b = 1 mod 16
b *= 2 – a*b; // a*b = 1 mod 256
b *= 2 – a*b; // a*b = 1 mod 65536
b *= 2 – a*b; // a*b = 1 mod 4294967296
return b;
}

Và khi w=64, ta chỉ cần 10 phép nhân. Với thời gian tính toán cỡ O(\log w) và không lệ thuộc vào giá trị của a, cách thứ ba này vừa bảo mật vừa nhanh hơn hai cách trước rất nhiều. Nó chỉ áp dụng được cho trường hợp w là lũy thừa của 2 (hơn là cho mọi w chẵn, điều kiện ứng dụng thuật toán mật mã này), chẳng hạn w = 8, 16, 32, 64,… nhưng dù sao đó cũng là trường hợp thực tế nhất.

(còn tiếp)

Ada

(tiếp theo)

Lịch sử và tư liệu. Thuật toán này được phát triển bởi một nhóm tác giả người Việt sống ở nhiều nước trên thế giới, hiện đang trong quá trình công bố. Mình không phải là một tác giả, nhưng có giao tiếp thư từ với một tác giả nên được lí giải đôi điều về thiết kế. Nhờ những thông tin đó mà có bài viết này.

Nhằm tạo dễ dàng cho việc sử dụng rộng rãi, thuật toán không được đăng kí sáng chế, nghĩa là không được xem là thuộc sở hữu trí tuệ của cá nhân nào mà được xem là thuộc tri thức chung (public domain).

Việc sử dụng thuần túy các phép toán đại số không tương thích với nhau (phép nhân, phép cộng và phép xor) để xây dựng thuật toán mã hóa là một í tưởng được thực thi đầu tiên ở thuật toán IDEA, do Xuejia Lai (Trung Quốc) và James L. Massey (Mĩ / Thụy Sĩ) sáng chế và giới thiệu năm 1991. IDEA dùng nhóm nhân modulo 2^w + 1, một nhóm có đúng 2^w phần tử khi và chỉ khi 2^w + 1 là một số nguyên tố. 2^{16} + 1 là một số nguyên tố, nhưng 2^{32} + 1 hay 2^{64} + 1 thì không. Điều đó đã giới hạn phạm vi ứng dụng cho IDEA ở những bộ vi xử lí 16 bit.

Tính không thể biểu diễn được bằng đa thức trên vành số nguyên modulo 2^w (w > 3) của phép xor được Otokar Grosek (Slovakia), Mirka Miller (Slovakia/Úc) và Joe Ryan (Úc) chứng minh năm 2004.

Tính biểu diễn được của mọi hàm nhờ một bộ hàm cơ sở gồm có phép cộng, phép quay đi 1 bit và hằng số 1 đã được Dmitry Khovratovich (Nga/Luxembourg) và Ivica Nikolic (Serbia/Luxembourg) chứng minh năm 2009.

Tính chất nhóm của phép nhân cải tiến định nghĩa bởi a \cdot b = 2ab + a + b được các tác giả phát hiện ra một cách độc lập với nhau (nhưng không công bố) trong khoảng thời gian từ năm 1990 đến 1994. Tính chất này cũng được phát hiện ra một cách độc lập bởi John H. Meyers và công bố trên Usenet năm 1997.

Tiêu chuẩn cần và đủ cho tính hoán vị của các đa thức trên vành số nguyên mod 2^w, bao gồm cả đa thức 2ab + (1 – 2e)(a – b + e) dùng trong thuật toán này, được Ronald L. Rivest (Mĩ) chứng minh và phát biểu năm 1999. Thuật toán RC6, do Rivest và các đồng nghiệp sáng chế và giới thiệu cùng năm đó, đã dùng một đa thức bậc 2 có dạng tương tự: e(1+2e).

Việc “nắn” mật mã cụm bằng một tham số dễ dàng thay đổi, thường thay đổi theo số thứ tự cụm, và cũng thường lệ thuộc vào một khóa, được triển khai lần đầu tiên ở chế độ vận hành LRW do 3 người Mĩ Moses Liskov, Ronald L. Rivest và David Wagner sáng chế và công bố vào năm 2002.

Việc tăng cường tính bảo mật bằng một (hay vài) khóa phụ, có thể có giá trị sử dụng lâu dài hơn khóa chính, đã được thực thi từ nhiều thập kỉ ở nhiều mật mã quốc gia. Thuật toán GOST 28147 của Liên Xô cũ (và Nga bây giờ), được sáng chế vào khoảng năm 1970 và công bố vào năm 1994, ngoài khóa chính 256 bit còn khuyến cáo giữ bí mật 8 bảng thế song ánh trên 4 bit, tức là tương đương với một khóa phụ có độ dài 8 \ast \log_2(2^4 !) \approx 354 bit.

Lưu đồ dữ liệu mã hóa cụm văn bản 4 từ bằng khóa 5 từ thuộc về thuật toán Skipjack, do cơ quan NSA (Mĩ) sáng chế trong khoảng thời gian từ năm 1987 đến năm 1993 và công bố vào năm 1998. Skipjack dùng một bảng thế 8 bit thành 8 bit áp dụng trên nửa từ và do đó, cũng chỉ hiệu quả ở các bộ vi xử lí 8 bit và 16 bit.

Thuật toán giới thiệu ở đây có thể thực hiện hiệu quả trên mọi bộ vi xử lí w bit, với w chẵn, chẳng hạn, 8 bit, 16 bit, 32 bit và 64 bit; w càng lớn thì mã hóa càng nhanh và độ bảo mật cũng càng cao.

Khả năng bảo mật của thuật toán này dựa trên khóa Z, còn các khóa T^{(0)} và U chỉ nên được xem là củng cố tính bảo mật. (Nhắc lại rằng T^{(0)} có được dùng hay không còn tùy theo chế độ vận hành.) Vì lẽ đó, các tác giả phân loại thuật toán ở độ bảo mật 5w bit, hơn là 10w bit. Điều này hẳn nhiên ảnh hưởng đến việc lựa chọn tham số trao đổi khóa (key exchange) và dẫn xuất khóa (key derivation). Ví dụ, để trao đổi khóa bằng phương pháp Diffie-Hellman trên nhóm các điểm của một đường cong elliptic xác định trên một trường số nguyên mod p (p nguyên tố) thì nên chọn đường cong với số điểm là một số 10w bit. Khi dẫn xuất các khóa, nên chọn 5w bit ngẫu nhiên làm khóa Z, rồi từ Z dẫn xuất T^{(0)} và U bằng một hàm băm mật mã (cryptographic hash function) có 10w bit trạng thái bên trong.

(–hết–)

Ada

Sau khi đăng loạt bài trên, mình nhận được phiên bản mới của thuật toán.

Phiên bản mới khác phiên bản cũ ở vị trí trộn giá trị thanh ghi nắn t0 vào thanh ghi văn bản. Phiên bản cũ trộn t0 trước hoặc sau hàm G. Phiên bản mới trộn t0 vào giữa hàm G. Kết quả là số phép tính và tốc độ tính toán thì không thay đổi, nhưng phiên bản mới mạnh hơn.

Mình đã cập nhật toàn bộ loạt bài theo phiên bản mới.

AdaMình vừa update loạt bài, bổ trợ thêm cách thứ ba để tính nghịch đảo, vừa bảo mật thông tin vừa nhanh hơn 2 cách đã trình diễn trước đây ( định lí Euler và thuật toán Euclid lan rộng ra ) .
Ada

Hôm nay, mình xin bổ sung cho loạt bài của mình 2 thuật toán dẫn xuất khóa nắn T^{(0)} và khóa đơn vị U từ khóa chính Z, được thiết kế bởi chính các tác giả của mật mã.

Thuật toán 1 là một mã cụm 5w bit, mã hóa Z thành (T^{(0)},U), với cấu trúc chuyên biệt cho mục đích đó. Nó chỉ gọi hàm mật mã có sẵn, vì vậy nó rất ngắn gọn.

Thuật toán 2 là một hàm băm mật mã có 10w bit trạng thái bên trong (đồng thời cũng là độ dài bản băm). Nó hoàn toàn độc lập với hàm mật mã có sẵn, nên nó khá dài. Nhưng bù lại, nó có thể dùng để băm những văn bản bất kì ở độ bảo mật 5w bit, ngang với mật mã.

THUẬT TOÁN 1. Để chạy một mã cụm, dĩ nhiên ta cần có trước một khóa cho nó. Trong trường hợp của ta, đó là một bộ ba Z_d, T_{d}^{(0)} và U_d với độ dài lần lượt 5w, 4w và w bit, được chọn ngẫu nhiên và độc lập với nhau. Khóa này để dùng lâu dài, dẫn xuất khóa nhiều lần. Nó được gọi là “khóa” vì theo truyền thống, đó là thông tin bảo mật. Nhưng trên thực tế, nó có thể bị lộ hoặc được công bố.

Cũng có thể chỉ bảo mật và bảo quản lâu dài Z_d, còn T_d^{(0)} và U_d thì để công khai và phù du (ephemeral), nghĩa là dùng một lần rồi quên ngay, mỗi lần cần dùng lại được chọn mới. Trong liên lạc, những thông tin công khai và phù du như thế thường được gọi là muối (salt). Nhờ đó, việc dẫn xuất (Z, Z_d) \mapsto (T^{(0)}, U) mất tính tất định, trở thành tựa như là ngẫu nhiên.

Khóa Z = Z_4 Z_3 Z_2 Z_1 Z_0, ở đây được xem là một cụm văn bản, được mã hóa thành khóa đơn vị U và khóa nắn T^{(0)} = T_3 T_2 T_1 T_0 bằng cách áp dụng thuật toán ENCRYPT đã trình bày trong loạt bài trên liên tiếp 5 lần, như sau.

x_1 x_0 u x_3 x_2 \leftarrow Z
x_3 x_2 x_1 x_0 \leftarrow \text{ENCRYPT}(x_3 x_2 x_1 x_0, Z_d, T_{d}^{(0)}, U_d)
u \leftarrow u \oplus x_3
x_3 x_2 x_1 x_0 \leftarrow \text{ENCRYPT}(x_3 x_2 x_1 x_0, Z_d, T_{d}^{(1)}, U_d)
x_0 \leftarrow x_0 \oplus u
x_3 x_2 x_1 x_0 \leftarrow \text{ENCRYPT}(x_3 x_2 x_1 x_0, Z_d, T_{d}^{(2)}, U_d)
x_3 \leftarrow x_3 \oplus u
x_3 x_2 x_1 x_0 \leftarrow \text{ENCRYPT}(x_3 x_2 x_1 x_0, Z_d, T_{d}^{(3)}, U_d)
u \leftarrow u \oplus x_0
x_3 x_2 x_1 x_0 \leftarrow \text{ENCRYPT}(x_3 x_2 x_1 x_0, Z_d, T_{d}^{(4)}, U_d)
U T^{(0)} \leftarrow u x_3 x_2 x_1 x_0

Trong đó, các nắn T_{d}^{(1)}, …, T_{d}^{(4)} được dẫn xuất từ T_{d}^{(0)} theo công thức T_{d}^{(j)} = T_{d}^{(0)} \cdot j hoặc bằng công thức truy hồi T_{d}^{(j+1)} = T_{d}^{(j)} + 2 \ast T_{d}^{(0)} + 1, như đã viết trong loạt bài trên.

Bằng hình ảnh, ta qui ước vẽ hàm số Y = \text{ENCRYPT}(X, Z, T, U), trong đó X = X_3 X_2 X_1 X_0 và Y = Y_3 Y_2 Y_1 Y_0, bằng một biểu tượng với vị trí các đầu vào và đầu ra như hình sau:

X3 X2 X1 X0
| | | |
+-+—+—+—+-+
| ENCRYPT <|<--- Z,U,T
+-+—+—+—+-+
| | | |
Y3 Y2 Y1 Y0

Hình 4. Biểu tượng hàm ENCRYPT.

Với qui ước đó, thuật toán được diễn tả bằng lưu đồ dữ liệu như thế này:

Z2 Z1 Z0 Z4 Z3
| | | | |
| +-+—+—+—+-+
| | ENCRYPT <|<----- Zd, Ud, Td(0)
| +-+—+—+—+-+ | | |
| | | | | | | |
+<---------o | | | | | [+]<--- 2*Td(0)+1
| | | | | | | |
| +-+—+—+—+-+ | | |
| | ENCRYPT <|<----- Zd, Ud, Td(1)
| +-+—+—+—+-+ | | |
| | | | | | | |
o———————>+ | | [+]<--- 2*Td(0)+1
| | | | | | | |
| +-+—+—+—+-+ | | |
| | ENCRYPT <|<----- Zd, Ud, Td(2)
| +-+—+—+—+-+ | | |
| | | | | | | |
o———>+ | | | | | [+]<--- 2*Td(0)+1
| | | | | | | |
| +-+—+—+—+-+ | | |
| | ENCRYPT <|<----- Zd, Ud, Td(3)
| +-+—+—+—+-+ | | |
| | | | | | | |
+<---------------------o | | [+]<--- 2*Td(0)+1
| | | | | | | |
| +-+—+—+—+-+ | | |
| | ENCRYPT <|<----- Zd, Ud, Td(4)
| +-+—+—+—+-+
| | | | |
U T3 T2 T1 T0

Hình 5. Mã hóa Z thành (T(0), U).

Ta thấy là U được tạo ra theo cách khác hẳn với T_0, T_1, T_2, T_3. Điều này là dễ hiểu: vì chúng sẽ được dùng theo hai cách khác hẳn nhau. Ta cũng thấy là Z_2 đã được dùng theo cách khác hẳn với Z_0, Z_1, Z_3, Z_4. Lí do cũng tương tự như thế: sau này, khi Z được dùng làm khóa mã hóa dữ liệu, các khóa con Z_0, …, Z_4 sẽ được dùng luân phiên theo cách giống nhau, nhưng Z_0, Z_1, Z_3, Z_4 đều được dùng đủ 13 lần còn Z_2 chỉ 12 lần.

Như vậy, cũng như thuật toán mật mã, thuật toán dẫn xuất khóa tuân theo một nguyên lí thiết kế nền tảng có tên là nguyên lí quyện. Năm 1949, nhà toán học Mĩ Claude E. Shannon trong tác phẩm tiên phong về khoa học mật mã Communication Theory of Secrecy Systems đã phát biểu hai nguyên lí: tán (diffusion) và quyện (confusion). Nguyên lí tán bảo rằng:

Từng số trong bản rõ phải tác động lên thật nhiều số trong bản mã. (Nói một cách khác, từng số trong bản mã phải phụ thuộc vào thật nhiều số trong bản rõ.)

Còn nguyên lí quyện bảo rằng:

Một số trong bản mã phải phụ thuộc thật phức tạp vào các số trong khóa (nói một cách khác, một số trong khóa phải tác động thật rắc rối lên các số trong bản mã), theo những cách rất khác nhau.

Theo nguyên lí quyện, diễn giải một cách thô thiển, những gì cần phải thật giống nhau thì hãy làm cho hơi khác nhau đi, những gì đã khá khác nhau rồi thì hãy làm cho khác hẳn nhau đi, và những gì đã khác hẳn nhau rồi thì hãy cố duy trì và đào sâu sự khác biệt ấy.

Nguyên lí này, khi được áp dụng một cách khoa học, sẽ làm cho mật mã mạnh hơn.

Bạn đọc chắc hẳn đều biết cái boomerang, một món khí giới ném tương truyền là của thổ dân châu Úc mà khi cầm dựng đứng hướng hai đầu cánh về phía trước mặt và ném thật mạnh, nó sẽ tự quay tít trên mặt phẳng của nó, bay trên một đường tròn (hay ellipse) trên mặt phẳng song song với mặt đất và quay trở về điểm xuất phát:
http://www.google.com/search?q=boomerang&rlz=1I7GZAZ_en&oe=UTF-8&um=1&ie=UTF-8&hl=en&tbm=isch&source=og&sa=N&tab=wi&ei=9x8jT53RHvCziQe27aXzBA&biw=1020&bih=849&sei=-h8jT5zbH6ShiAeqqPzpBA

Người ta thường bảo nó có hình quả chuối, hay hình chữ V, chữ U, hay hình đôi cánh máy bay. Tính đối xứng (giống nhau của hai cánh) là đặc điểm cơ bản của nó. Nhưng nếu cầm nó và xem kĩ, sẽ thấy những sự mất đối xứng nhỏ: hai mặt có độ cong khác nhau, hai cánh có độ nghiêng so với mặt phẳng chung ngược nhau và có cạnh sắc (hoặc cạnh cùn) quay về hai phía đuổi theo nhau. Đúng hơn, có thể mô tả nó giống như một cái chong chóng 3 cánh đã bị cắt mất đi 1 cánh. Đó là sự mất đối xứng lớn. Chính những sự mất đối xứng nhỏ (hơi khác nhau) và lớn (khác hẳn nhau) mà chỉ có khoa học khí động lực mới lí giải được ấy đã giúp cho nó tự quay tít hơn, bay ổn định hơn và quay về chính xác hơn bất cứ quả chuối nào.

Ada

Mình gửi 1 file dạng PDF chứa một phiên bản mở rộng của loạt bài của mình. Thêm một ít phân tích và lí giải.

Xem thêm: Lịch sử Internet – Wikipedia tiếng Việt

Ada

Mình nhận được phiên bản 3 của thuật toán. Hàm G trước gồm 2 phép nhân nay sửa lại thành 1 phép nhân và 1 phép chia. Phiên bản mới vẫn nhanh như trước nhưng nghe đâu mạnh hơn và làm cho mã hóa và giải mã mạnh đều nhau hơn.

Loạt bài mình không update nữa, giữ nguyên phiên bản 2. File PDF đính kèm thì mình update lên phiên bản 3. Nhân tiện, chữa một số lỗi sai về toán.

vBulletin ® Version 4.2.2, Copyright © 2023 vBulletin Solutions, Inc. All rights reserved. Administer by Kevin Hoang

Source: https://thomaygiat.com
Category : Kỹ Thuật Số