MỤC LỤC

DANH MỤC HÌNH ẢNH.....................................................................................3
DANH MỤC VIẾT TẮT......................................................................................4
TÓM TẮT NỘI DUNG........................................................................................5
LỜI NÓI ĐẦU....................................................................................................6
CHƯƠNG I : TÌM HIỂU CHUNG VỀ BITCOIN.................................................9
1. Khái niệm Blockchain.................................................................................9
2. Khái niệm bitcoin........................................................................................9
3. Nguyên lý hoạt động của Bitcoin.............................................................11
4. Nền tảng kỹ thuật....................................................................................12
CHƯƠNG II : THUẬT TOÁN BĂM SHA.........................................................14
1. Khái niệm..................................................................................................14
2. Đặc tính của hàm băm..............................................................................14
3. Ứng dụng của hàm băm...........................................................................14
4. Cấu trúc của hàm băm..............................................................................15
5. Tính chất của hàm băm............................................................................15
6. Các loại hàm băm......................................................................................15
6.1.
Hàm băm MD4 (Message Disgest 4) và MD5 (Message Disgest 5)
15
6.2.
Hàm băm SHS (Secure Hash Standard).........................................16
CHƯƠNG III : THUẬT TOÁN BĂM SHA 256.................................................17
1. Khái niệm..................................................................................................17
2. Mô tả thuật toán.......................................................................................17
2.1.
Các tham số, ký hiệu và thuật ngữ................................................18
2.2.
Phép toán.........................................................................................18
2.3.

Chuyển đổi dữ liệu.........................................................................19
2.5.
Các hàm chức năng sử dụng trong SHA-256................................20
2.6.
Các hằng số sử dụng trong SHA-256............................................20
2.8.
Thuật toán băm SHA-256...............................................................22
CHƯƠNG IV : DEMO THUẬT TOÁN SHA-256 bằng PHP............................25
1. Viết chương trình.....................................................................................25
2. Thử nghiệm...............................................................................................32
2.1.
Giao diện chương trình..................................................................33
2.2.
Kiểm thử..........................................................................................35
KẾT LUẬN.......................................................................................................37
1


TÀI LIỆU THAM KHẢO...................................................................................38

2


DANH MỤC HÌNH ẢNH

Hình 1: Sơ đồ hoạt động của Blockchain..................................................................7
Hình 2 : Ví điện tử Trezor................................................................................................. 8
Hình 3-bit Mảng 64 hằng số 32-bit Kj{256}..............................................................18
Hình 4 : Các giá trị khởi tạo của giá trị băm..........................................................19
Hình 5: Giao diện chương trình khi mới khởi chạy...........................................28

Hình 6 : Giao diện trước khi bấm nút tính toán...................................................29
Hình 7: Kết quả thu được sau khi thực hiện băm...............................................30

3


DANH MỤC VIẾT TẮT
Ký hiệu
BTC

Tên đầy đủ

Ý nghĩa
Ký hiệu đồng tiền ảo
Bitocin
Giải thuật băm an toàn
Processing Chuẩn bảo mật an toàn

SHA
FIPS

Secure Hash Algorithm
Federal
Information

NIST

Standard
của chính phủ Mỹ
National Institute of Standards and Viện Tiêu chuẩn và Kĩ


PHP

Technology
Hypertext Preprocessor

thuật Quốc gia
Ngôn ngữ lập trình kịch

Secure Hash Standard

bản
Bộ mã hóa thuật toán

National Security Agency

băm an toàn
Phép toán thao tác bit
Cơ quan An ninh Quốc

SHS
XOR
NSA

gia Hoa Kỳ
các giải thuật đồng hóa

MD4, MD5 Message Digest 4, 5

thông tin


4


TÓM TẮT NỘI DUNG
Bài báo cáo tìm hiểu về thuật toán mã hóa đồng tiền ảo Bitcoin ngoài
phần mở đầu, kết luận thì có nội dung chính được chia làm 4 ch ương:
Chương 1 : Tìm hiều chung về Bitcoin: Tìm hiểu khái quát v ề đ ồng
tiền Bitcoin như khái niệm, blockchain, nguyên lý hoạt động, nền tản kỹ
thuật của đồng tiền ảo Bitcoin.
Chương 2 : Thuật toán băm SHA : Tìm hiểu chung về khái niệm, đặc
điểm, tính chất, cấu trúc của hàm băm SHA.
Chương 3: Thuật toán băm SHA 256 : Tìm hiều khái niệm, nh ững
bước tiền xử lý và cách thức hoạt động của thuật toán SHA 256.
Chương 4 : Demo : Tạo và chạy thử nghiệm thuật toán bằng ngôn
ngữ PHP và kiểm tra, so sánh kết quả thu được với kết quả trên mạng
Internet.

5


LỜI NÓI ĐẦU
Ngày nay, xã hội càng phát triển, thế giới bùng nổ việc áp dụng công
nghệ thông tin vào mọi hoạt động kinh tế. Đặc biệt Internet đ ược đ ưa và
ứng dụng trong các hoạt động thương mại đã tạo nên một lĩnh v ực m ới là
thương mại điện tử. Thương mại điện tử đã xóa nhòa đi biên giới giữa các
quốc gia tạo nên một thị trường giao dịch chung gọi là thị trường toàn cầu.
Thương mại điện tử mang lại những tiện ích to lớn như tăng hiệu suất,
nâng cao năng lực cạnh tranh, giảm chi phí, tăng lợi nhuận...
Thương mại trên mạng Internet đã gần như hoàn toàn coi các t ổ

chức tài chính là bên thứ ba được tin cậy để xử lý các thanh toán điện t ử.
Trong khi làm việc khá tốt đối với hầu hết các giao d ịch, hệ th ống này v ẫn
tồn tại những điểm yếu cố hữu của mô hình tín nhiệm (the trust based
model). Các giao dịch mà hoàn toàn không thể đảo ngược không th ực s ự là
có thể xảy ra được, vì các tổ chức tài chính không thể tránh được các tranh
chấp trung gian. Chi phí trung gian làm tăng cao các chi phí giao d ịch, h ạn
chế mức giao dịch tối thiểu và làm giảm khả năng giao d ịch v ới các m ức
giao dịch nhỏ thông thường, và phải mất chi phí cao h ơn đ ể th ực hiện các
thanh toán không thể đảo ngược cho các dịch vụ không thể đảo ngược. Với
khả năng đảo ngược, nhu cầu tín nhiệm đã lan rộng. Các th ương gia ph ải
thận trọng với khách hàng của họ, sách nhiễu họ bởi nhiều thông tin h ơn
bình thường họ cần. Một tỉ lệ gian lận nhất định đã được công nh ận là
không thể tránh khỏi. Các chi phí và thanh toán không chắc chắn này có th ể
tránh được bằng cách sử dụng tiền tệ vật lý, nhưng không có c ơ ch ế nào
tồn tại để thực hiện các thanh toán qua một kênh thông tin liên lạc mà
thiếu một bên được tin cậy.
Vậy thứ ta cần là một hệ thống thanh toán điện tử dựa vào bằng
chứng mật mã thay vì tín nhiệm, cho phép hai bên sẵn sàng có th ể giao
dịch trực tiếp với nhau mà không cần đến một bên thứ ba được tin c ậy nào
cả. Các giao dịch được tính toán để không đảo ngược được sẽ bảo vệ người
6


bán khỏi gian lận, và các cơ chế ký quỹ có thể được thực hiện dễ dàng
nhằm bảo vệ người mua. Đồng tiền ảo Bitcoin chính là một trong nh ững
giải pháp bảo đảm được điều này với tính bảo mật cao, khó bị làm gi ả hay
đánh cắp. Bài báo cáo này sẽ tìm hiểu về thuật toán SHA 256 dùng đ ể mã
hóa đồng tiền ảo Bitcoin, tạo nên tính bảo mật an toàn cao cho nó.
Chúng em xin chân thành cám ơn cô Nguyễn Thị Thu Thủy đã tạo
điều kiện và tận tình giúp đỡ trong quá trình chúng em làm bài báo cáo này.

Do kiến thức còn hạn hẹp nên bài báo cáo còn nhiều thiếu sót, chúng em sẽ
cố gắng khắc phục trong thời gian tới.

Chân thành cám ơn!

7


8


CHƯƠNG I : TÌM HIỂU CHUNG VỀ BITCOIN
1. Khái niệm Blockchain
Blockchain (Chuỗi khối) là một cơ sở dữ liệu phân cấp lưu trữ thông
tin trong các khối thông tin được liên kết với nhau bằng mã hóa và m ở
rộng theo thời gian. Mỗi khối thông tin đều ch ứa thông tin v ề th ời gian
khởi tạo và được liên kết tới khối trước đó, kèm một mã th ời gian và d ữ
liệu giao dịch. Blockchain được thiết kế để chống lại việc thay đổi của
dữ liệu: Một khi dữ liệu đã được mạng lưới chấp nh ận thì sẽ không có
cách nào thay đổi được nó.
Blockchain được đảm bảo nhờ cách thiết kế sử dụng hệ thống tính
toán phân cấp với khả năng chịu lỗi byzantine cao. Vì v ậy s ự đ ồng
thuận phân cấp có thể đạt được nhờ Blockchain. Vì vậy Blockchain phù
hợp để ghi lại những sự kiện, hồ sơ y tế, xử lý giao dịch, công ch ứng,
danh tính và chứng minh nguồn gốc. Việc này có tiềm năng giúp xóa bỏ
các hậu quả lớn khi dữ liệu bị thay đổi trong bối cảnh thương mại toàn
cầu.
Cách thức hoạt động của Blockchain được miểu tả như hình sau:

Hình 1: Sơ đồ hoạt động của Blockchain

9


2. Khái niệm bitcoin
Tiền thuật toán là một loại tiền tệ kỹ thuật số, được sinh ra bởi
các thuật toán mã hóa phức tạp dưới dạng phần mềm mã nguồn m ở.
Bitcoin (ký hiệu: BTC, XBT, ) là một loại tiền thuật toán, được phát
minh bởi một người bí ẩn sử dụng bút danh Satoshi Nakamotodưới
dạng phần mềm mã nguồn mở từ năm 2009. Bitcoin có thể được trao
đổi trực tiếp bằng thiết bị kết nối Internet ngang hàng mà không c ần
thông qua một tổ chức tài chính trung gian nào. Do đó không cần ph ải
trả lệ phí giao dịch và cũng không cần phải cung cấp tên th ật.
Đối với Bitcoin, có thể hình dung Blockchain là m ột cu ốn s ổ cái ghi
lại tất cả các giao dịch. Dữ liệu trong cuốn sổ cái liên tục đ ược m ạng
lưới máy tính ngang hàng trên thế giới cập nhật và bảo trì. Giao d ịch khi
A gửi X bitcoin cho B được ghi lại trên toàn hệ thống, tất cả các máy tính
trong mạng này sẽ xác minh và ghi lại giao dịch đó vào cu ốn s ổ cái r ồi
cấp phát dữ liệu này tới các máy tính khác.
Rất nhiều doanh nghiệp đã bắt đầu chấp nhận cho việc s ử d ụng
bitcoin. Thậm chí,vào một ngày tháng 05 năm 2010, m ột l ập trình viên
tên Laszlo Hanyecz đã trả 10.000BTC để mua 2 chiếc bánh pizza.
Cần phải có một phần mềm ví để lưu trữ cũng như quản lý nguồn
chi tiêu bitcoin. Mỗi ví Bitcoin bao gồm địa chỉ Bitcoin công khai (hash của
public key) và khóa riêng tư (private key). Một địa ch ỉ có 160 bit d ữ li ệu, vì
vậy có thể tạo ra tổng cộng 2160 địa chỉ Bitcoin - tương đ ương 1048 đ ịa
chỉ (để so sánh: Có tổng cộng khoảng 1047 phân tử n ước trên trái đất).
Ngoài ra địa chỉ còn bao gồm 4 byte checksum nên xác suất mạng l ưới ch ấp
nhận địa chỉ Bitcoin gõ sai cực kỳ thấp.
Bất kỳ ai cũng có thể gửi Bitcoin đến một chiếc ví bằng địa ch ỉ công
khai, còn khoá riêng tư phải được nhập khi ch ủ ví muốn g ửi Bitcoin đi. Vì

vậy, việc sở hữu Bitcoin được định nghĩa là sự nắm giữ khoá riêng t ư của 1
địa chỉ Bitcoin. Một khi khoá riêng tư bị mất, mạng l ưới Bitcoin sẽ không
10


thể xác nhận được việc sở hữu số bitcoin đó, và số bitcoin trong địa ch ỉ đó
sẽ vĩnh viễn bị mất. Ví cho phép người dùng hoàn tất thanh toán gi ữa các
địa chỉ khác nhau bằng cách cập nhật vào Blockchain. Khi th ực hiện giao
dịch bằng thiết bị di động, người dùng có th ể s ử dụng mã QR đ ể đ ơn gi ản
hoá quy trình thanh toán.

Hình 2 : Ví điện tử Trezor
Bitcoin có thể được mua bán thông qua các sàn giao dịch, hoặc th ậm
chí ở một số nơi trên thế giới, kể cả ở Việt Nam đã có máy ATM dành riêng
cho bitcoin. Người dùng có thể rút trực tiếp tiền mặt từ bitcoin bằng
những bitcoin ATM này.
Bitcoin không thể in như tiền mặt, chúng được tạo ra bởi m ột hệ
thống máy tính trên toàn cầu. Quy mô của mạng lưới này càng ngày c ảng
rộng với sức mạnh từ những siêu máy tính tham gia.
Chính vì tính chất ẩn danh và không thể bị kiểm soát b ởi chính ph ủ cho
nên đồng bitcoin trở nên hấp dẫn ngườ dùng.
3. Nguyên lý hoạt động của Bitcoin
Giá trị của Bitcoin cũng giống như các loại tiền tệ khác, đ ược xác
định theo quy luật cung – cầu. Để xử lý giao dịch, hệ thống máy tính cần
phải thực hiện thủ tục gọi là”Đào bitcoin”. Bao gồm việc giải mã một
phương trình toán học và đưa ra đáp án gồm 64 ký tự. Khi bài toán
11


được giải mã thành công, một khối Bitcoin bao gồm thông tin các giao

dịch trong đó sẽ hoàn tất việc xử lý.
Thợ mỏ - những người đào Bitcoin, sẽ được thưởng một lượng
Bitcoin từ mạng máy tính cho thành quả của mình. Độ khó mỗi bài toán
sẽ tăng theo chu kỳ để đám bảo Bitcoin luôn được tạo m ới sau m ỗi 10
phút.
Đồng tiền Bitcoin có thể được chia nhỏ thành nhiều đơn vị con. 1
Bitcoin bằng 100 triệu Satoshi – Shatori là đ ơn v ị nh ỏ nh ất c ủa đ ồng
Bitcoin được đặt theo tên của người đã tạo ra nó.
4. Nền tảng kỹ thuật
Trong quá trình đào bitcoin, phần cứng khai thác bitcoin của
bạn chạy một hàm băm mật mã (hashing) (2 vòng SHA256) trên một
khối. Với mỗi hàm băm mới được thử, phần mềm đào bitcoin sẽ s ử
dụng một số khác nhau làm phần tử ngẫu nhiên của kh ối, số này
được gọi là nonce. Tùy thuộc vào nonce và ch ức năng băng trong kh ối
sẽ tạo một băm giống như dưới đây:
93ef6f358fbb998c60802496863052290d4c63735b7fe5bdaac821de96a
53a9a
Bạn có thể thấy hàm băm này rất dài. (Đó là một số th ập l ục
phân, các chữ cái từ A-F là đại diện cho các chữ số từ 10 đến 15).
Mục tiêu khó khăn (difficulty target) sẽ đảm bảo rằng các kh ối sẽ
được tạo ra khoảng mười phút một lần. Để tạo ra m ột kh ối hợp lệ,
các thợ mỏ phải tìm một hàm băm sao cho nó nhỏ h ơn m ục tiêu khó
khăn. Vì vậy nếu ví dụ mục tiêu là:
100000000000000000000000000000000000000000000000000
0000000000000
Thì bất kỳ số nào bắt đầu bằng số 0 sẽ đạt yêu cầu, ví d ụ:
0787a6fd6e0782f7f8058fbef45f5c17fe89086ad4e78a1520d06505acb4
522f
12



Nếu chúng ta hạ thấp mục tiêu xuống:
010000000000000000000000000000000000000000000000000
0000000000000
Bây giờ chúng ta cần thêm 2 số 0 vào đầu m ục tiêu đ ể đ ược
như
sau:00db27957bd0ba06a5af9e6c81226d74312a7028cf9a08fa125e49f
15cae4979
Do mục tiêu là một dãy số khổng lồ với hàng ch ục ch ữ số,
người ta thường sử dụng một số đơn giản để làm mục tiêu hiện tại.
Con số này là đại diện cho độ khó trong việc khai thác (mining
difficulty). Chỉ số cho biết mức độ khó khăn khi khai thác kh ối hi ện
tại so với khi khai thác khối đầu tiên. Vì vậy, độ khó có giá tr ị 70000
có nghĩa là để tạo ra các khối hiện tại bạn phải làm khối lượng công
việc gấp 70000 lần so với lúc Satoshi Nakamoto đã phải làm đ ể tạo
ra các khối đầu tiên. Để công bằng, thì phần cứng đào bitcoin và các
thuật toán chậm hơn rất nhiều và ít được tối ưu hóa. Để gi ữ cho các
khối sẽ được tạo ra mỗi 10 phút, độ khó sẽ được điều chỉnh sau m ỗi
2016 blocks. Với sức mạnh hiện tại của mạng lưới toàn cầu, hiện tại
sẽ mất khoảng 14 ngày để hoàn thành 2016 khối nh ư vậy. Đó là lý do
tại sao, khi sức mạnh của mạng lưới tăng lên, độ khó cũng sẽ tăng
lên.

13


CHƯƠNG II : THUẬT TOÁN BĂM SHA
1. Khái niệm
Hàm băm là thuật toán không dùng khóa để mã hóa (ở đây dùng
thuật ngữ “băm” thay cho “mã hóa”), nó có nhiệm v ụ “lọc” (băm) tài li ệu

(bản tin) và cho kết quả là một giá trị “băm” có kích th ước c ố đ ịnh, còn
gọi là “đại diện tài liệu” hay “đại diện bản tin”, “đại diện thông đi ệp”.
Hàm băm là hàm một chiều, theo nghĩa giá trị hàm băm là duy nhất,
và từ giá trị băm này, khó có thể suy ngược lại được nội dung hay độ dài
ban đầu của tài liệu gốc.
2. Đặc tính của hàm băm
Hàm băm h là hàm một chiều (One – wat Hash) với các đặc tính sau:
 Với tài liệu đầu vào (bản tin gốc) x, chỉ thu được giá trị băm duy
nhất z = h(x).
 Nếu dữ liệu trong bản tin x bị thay đổi hay bị xóa để thành bản
tin x’, thì giá trị băm h(x’) ≠ h(x). Cho dù chỉ là một sự thay đổi nhỏ,
ví dụ chỉ thay đổi 1 bit dữ liệu của bản tin gốc x, thì giá trị băm
h(x) của nó cũng vẫn thay đổi. Điều này có nghĩa là: hai thông điệp
khác nhau, thì giá trị băm của chúng cũng khác nhau
 Nội dung của bản tin gốc “khó” thể suy ra từ giá trị băm của nó.
Nghĩa là: với thông điệp x thì “dễ” tính được z=h(x), nhưng lại khó
tính ngược lại x nếu chỉ biết giá trị băm h(x) (kể cả khi biết hàm
băm h).
3. Ứng dụng của hàm băm
 Với bản tin dài x, thì chữ ký trên x cũng sẽ dài, như vậy tốn thời
gian “ký”, tốn bộ nhớ để lưu giữ “chữ ký”, tốn rất nhiều thời
gian để truyền “chữ ký” trên mạng. Người ta dùng hàm băm h
để đại cho bản tin z = h(x) nó có độ dài ngắn (ví dụ 128 bit).
Sau đó ký trên z, như vậy chữ ký trên z sẽ nhỏ hơn rất nhiều so
với chữ ký trên bản tin gốc x.
 Hàm băm dùng để xác định tính toàn vẹn dữ liệu.
14


 Hàm băm dùng để bảo mật một số dữ liệu đặc biệt, ví dụ bảo

vệ mật khẩu, bảo vệ khóa mật mã, ...
4. Cấu trúc của hàm băm
Hầu hết các hàm băm mật mã đều có cấu trúc giải thuật như sau:
Cho trước một thông điệp M có độ dài bất kỳ. Tùy theo thuật toán
được sử dụng, chúng ta có thể cần bổ sung một số bit vào thông điệp này
để nhận được thông điệp có độ dài là bội số của một h ằng s ố cho tr ước.
Chia nhỏ thông điệp thành từng khối có kích th ước bằng nhau: M1, M2, …
Ms
Gọi H là trạng thái có kích thước n bit, f là “hàm nén” th ực hiện thao
tác trộn khối dữ liệu với trạng thái hiện hành.
* Khởi gán H0 bằng một vector khởi tạo nào đó
* Hi = f(Hi-1,M) với i = 1, 2, 3, …, s
Hs chính là thông điệp rút gọn của thông điệp M ban đ ầu.
5. Tính chất của hàm băm
Tính chất 1: Hàm băm không va chạm yếu.
Hàm băm h được gọi là không va chạm yếu , nếu cho trước bức
điện x, “khó có thể” tính toán để tìm ra bức điện x’ ≠ x mà h(x’) = h(x).
Tính chất 2: Hàm băm không va chạm mạnh.
Hàm băm h được gọi là không va chạm mạnh nếu “khó” thể
tính toán để tìm ra hai bức thông điệp khác nhau x và x’ (x’≠ x) mà có h(x’)
= h(x).
Tính chất 3: Hàm băm h là hàm một chiều.
Hàm băm h được gọi là hàm một chiều nếu khi cho trước một bản
tóm lược thông báo z thì “khó thể” tính toán để tìm ra thông điệp ban đầu x
sao cho h(x) = z.
6. Các loại hàm băm
6.1. Hàm băm MD4 (Message Disgest 4) và MD5 (Message
Disgest 5)
15



Hàm băm MD4 được Giáo sư Ron Rivest đề nghị vào năm 1990. Vào
năm 1992, phiên bản MD5 của thuật toán này ra đ ời. Thông đi ệp r út gọn có
độ dài 128 bit.
Năm 1995, Hans Dobnertin đã chỉ ra sự đụng độ ngay chính trong
bản than hàm nén của giải thuật (mặc dù chưa th ật s ự phá v ỡ đ ược gi ải
thuật). Năm 2004, nhóm tác giả Xiaoyun Wang, Denguo Feng, Xuejia Lai và
Hongbo Yu đã công bố kết quả về việc phá vỡ thuật toán MD4 và MD5
bằng phương pháp tấn công đụng độ
6.2. Hàm băm SHS (Secure Hash Standard)
Hàm băm SHS do NIST và NSA xây dựng được công bố trên Federal
Register vào ngày 31/1/1992, và sau đó chính th ức tr ở thành ph ương pháp
chuẩn từ ngày 13/5/1993. Thông điệp rút gọn có đ ộ dài 160bit.
Ngày 26/08/2002, Viện tiêu chuẩn và công nghệ quốc gia Hoa Kỳ đã
đề xuất hệ thống chuẩn hàm băm an toàn gồm 4 thuật toán hàm băm SHA1, SHA-256, SHA-384, SHA-512. Đến 25/03/2004, NIST đã chấp nhận thêm
thuật toán hàm băm SHA-224 vào hệ thống chuẩn hàm băm. Các thuật toán
hàm băm do NIST đề xuất được đặc tả trong tài liệu FIPS180-2

16


CHƯƠNG III : THUẬT TOÁN BĂM SHA 256
1. Khái niệm
SHA-2 (Secure Hash Algorithm 2) là tập hợp các hàm băm mật mã
được thiết kế bởi NSA. Hàm băm mật mã là các phép toán ch ạy trên d ữ
liệu kỹ thuật số, bằng cách so sánh các tính toán “băm” (đầu ra từ th ực
hiện các thuật toán) đến các giá trị hash được biết đến và mong đ ợi,
một người có thể xác định tính toàn vẹn của dữ liệu. Ví dụ, tính toán các
hash của một tệp tin tải về và so sánh kết quả vào một kết quả băm
được phát hành trước đó có thể xác định các tệp tin tải về có bị sửa đ ổi

hoặc giả mạo hay không. Một khía cạnh quan trọng của hàm băm m ật
mã là chúng kháng xung đột: Giá trị đầu vào khác nhau thì giá tr ị đ ầu ra
sẽ không giống nhau.
SHA-256 là một loại hàm băm của SHA-2, là hàm băm tính toán v ới
các từ 32-bit.
2. Mô tả thuật toán
Mỗi thuật toán có thể được mô tả trong hai giai đoạn: tiền x ử lý và
tính toán băm. Tiền xử lý liên quan đến việc đệm một thông điệp, phân
tích cú pháp thông điệp đó thành các khối m-bit, và thiết lập các giá tr ị
khởi tạo sẽ được sử dụng trong tính toán băm. Việc tính toán băm sinh
ra một thông điệp lịch trình (message schedule) từ thông điệp đã đệm
và sử dụng lịch trình, cùng với chức năng, hằng số, và các hoạt động từ
ngữ để lặp đi lặp lại tạo ra một loạt các giá trị băm. Các băm thức giá trị
được tạo ra bởi việc tính toán hash được sử dụng để xác định các thông
điệp tóm lược (message digest).
Thuật toán băm SHA-256 có thể chia làm hai giai đoạn: tiền x ử lý và
tính toán băm. Giai đoạn tiền xử lý đưa thông tin cần băm ( M ) v ề dạng
chuẩn, phân tích M thành m-bit block, và cài đặt giá trị ban đầu cho giai
đoạn tính toán băm. Giai đoạn tính toán băm sinh ra thông điệp li ệt kê
của M từ thông điệp chuẩn, và sử dụng liệt kê đó cùng v ới các ch ức
17


năng, các hằng số, các phép toán để sinh một dãy các giá tr ị băm. Giá tr ị
băm cuối cùng sinh bởi giai đoạn tính toán băm được sử dụng làm giá tr ị
băm của M.
2.1. Các tham số, ký hiệu và thuật ngữ
M

thông điệp được băm


a, b, c, …, h các biến thay đổi có độ dài w-bit s ử dụng trong tính toán
giá trị băm
H(i)

giá trị băm thứ i, H(0) là giá trị khởi tạo, H(N) là giá trị
băm cuối cùng, sử dụng làm giá trị băm

Hj(i)

từ thứ j của giá trị băm thứ i, H 0(i) là từ trái nhất của giá
trị băm thứ i

Kt

hằng số sử dụng cho vòng lặp thứ t của tính toán băm

k

Số số 0 thêm vào thông điệp M trong quá trình tạo
thông
điệp chuẩn

l

độ dài của thông điệp M tính theo bit

m

số bit trong 1 block


M(i)

Block thứ i

Mj(i)

từ thứ j của block thứ i, M 0(i) là từ trái nhất của block i

w

số bit của một từ

T

w-bit tạm thời sử dụng trong tính toán băm

N

số block của thông điệp chuẩn

Wt

w-bit thứ t của thông điệp liệt kê

2.2. Phép toán
18


^


phép toán end



phép toán or



phép toán cộng bit XOR



phép phủ định

+

phép cộng theo modulo 2w

<<

phép dịch trái, ở đây x<
bit
>>

phép dịch phải, x>>n có nghĩa là x được dịch phải n bit

2.3. Chuyển đổi dữ liệu
Một số ở dạng hexa là một mảng của tập {0, 1, 2, … 9, a, b, …, f}. M ột

số hex là sự biểu diễn của chuỗi 4 bit. Ví dụ số hex “7” là bi ểu diễn c ủa 4
bit “0111”, số hex “a” là biểu diễn của chuỗi 4 bit “1010”.
Một từ là chuỗi w-bit có thể sử dụng ở dạng hex. Để chuy ển một t ừ
sang dạng số hex, mỗi chuỗi 4 bit được tương ứng chuy ển sang s ố hex. Ví
dụ với chuối 32 bit :
“1010 0001 0000 0011 1111 1110 0010 0011”
Được chuyển thành “a103fe23” dưới dạng số hex
Một số nguyên có thể được biểu diễn bằng một từ hoặc một số t ừ.
Một số nguyên nằm giữa 0 và 232 – 1 có thể biểu diễn như là chuỗi 32 bit.
Ví dụ số nguyên 291 = 256 + 32 + 2
+ 1 = 28 + 25 + 2 + 1 được biểu diễn dưới dạng 32 bit là :
“0000 0000 0000 0000 0000 0001 0010 0011”
Và được biểu diễn dưới dạng số hex là : “ 00000123”
19


2.4. Các phép toán
Phép cộng modulo 2w : phép cộng modulo x+y được đ ịnh nghĩa nh ư
sau: x,y là biểu diễn của 2 số nguyên dương X và Y với 0 < X < 2w và 0 < Y<
2w , chuyển số nguyên Z thành chuỗi z được phép cộng theo modulo 2w : z
=x+y
SHRn (x) : là phép dịch phải, với x là từ w-bit và n là s ố nguyên d ương
với
0 < n < w được định nghĩa :
SHRn (x) = x >> n
ROTRn (x) :
ROTRn (x) = (x>>n) v (x<< w-n)
ROTLn (x) :
ROTLn (x) = (x<<n) v (x>> w-n)
2.5. Các hàm chức năng sử dụng trong SHA-256

SHA-256 sử dụng 6 hàm chức năng , mỗi hàm chức năng làm việc trên
các từ 32- bit được ký hiệu là x,y và z. Kết quả tr ả về c ủa các hàm cũng là
chuỗi 32-bit. Các hàm chức năng trong SHA-256 là :
Ch (x,y,z) = (x ^ y)  (  x ^ z)
Maj (x,y,z) = (x ^ y)  (x ^ z)  (y ^ z)
= ROTR28(x) ⊕ ROTR34(x) ⊕ ROTR39 (x)
= ROTR14(x) ⊕ ROTR18(x) ⊕ ROTR41(x)
(x) = ROTR1(x) ⊕ ROTR8(x) ⊕ SHR7(x)
(x) = ROTR19(x) ⊕ ROTR61(x) ⊕ SHR6(x)
2.6. Các hằng số sử dụng trong SHA-256
20


SHA-256 sử dụng một mảng 64 hằng số 32-bit, K 0{256}, K1{256}…,
K63{256}.. Những từ 32-bit này được lấy từ 32 bit đầu tiên của ph ần
phân số trong kết quả của phép lấy căn bậc 3 của 64 s ố nguyên t ố
đầu tiên.
Ở hệ hex, những hằng số đó là (từ trái qua phải):

Hình 3: Mảng 64 hằng số 32-bit Kj{256}
2.7. Quá trình xử lý thông điệp M
Thông điệp M sẽ được xử lý vê dạng chuẩn trước khi tính toán băm. Quá
trình xử lý này bao gồm ba phần : chuẩn hóa M, phân tích M thành các block
và khởi tạo giá trị băm.
Chuẩn hóa M: Giả sử M có độ dài L bit. Thêm bit 1 vào sau thông đi ệp
M, sau đó thêm k bit 0 , ở đây k là số nguyên nh ỏ nh ất v ới đi ều kiện
L + 1 + k = 448 mod 512.
Sau đó thêm 64-bit là biểu diễn nhị phân của L. Ví d ụ thông điệp M là
“abc” (biểu diễn dưới dạng 8 bit – ASCII) có độ dài 8x3 = 24 bit. Quá trình x ử
lý M sẽ thêm bit 1 vào sau thông điệp, sau đó thêm 448 – (24+1) = 423 bit 0,

sau đó thêm 64-bit là biểu diễn nhị phân của 24. Ta thu đ ược thông đi ệp đã
được xử lý dạng :

21


Thông điệp M thu được sẽ có độ dài là bội số của 512
Phân tích thông điệp M : thông điệp M được phân tích thành N kh ối 512 bit, M (1),
M(2),…,M(N). Mỗi khối 512-bit có thể được biểu diễn như là 16 từ 32-bit. 32 bit đầu
tiên
của block thứ i là M0(i), 32 bit tiếp theo là M1(i) và 15
tới M (i)
Cài đặt giá trị khởi tạo của giá trị băm (H (0)): trước khi tính toán băm bắt
đầu giá trị băm H(0) cần được cài đặt ở dạng hex như sau:

Những giá trị trên được lấy từ 32 bit đầu tiên trong kết quả của phép
lấy căn bậc hai của 8 số nguyên tố đầu tiên.

2.8. Thuật toán băm SHA-256
SHA-256 có thể được sử dụng để băm các thông đi ệp M có đ ộ dài L
bit,

Hình 4 : Các giá trị khởi tạo của giá trị băm
22


0 < L < 264.
Thuật toán sử dụng :
1. Thông điệp M đã được xử lý chuẩn hóa
2.

Mảng 64 từ 32-bit W0 , …, W63

3. 8 biến tạm có nhãn a, b, c, d, e, f, g, h, m ỗi bi ến là m ột chuỗi 32bit
4.

Một giá trị băm ban đầu là 8 chuỗi 32-bit,có nhãn H 0(0),…,

H7(0)
5. Sử dụng 2 biến tính toán T1, T2 là các chuỗi 32-bit Quá trình tính
toán băm :
For i=1 to N:
{
1. Chuẩn bị thông điệp lịch trình {Wt} :

2. Khởi tạo tám biến làm việc a, b, c, d, e, f, g, h với (i-1)st giá trị :
a=
b=
c=
d=
e=
f=
g=
h=
3. For t=0 to 63:
23


{

h=g
g=f
f=e
e = d + T1
d=c
c=b
b=a
a = T 1 + T2
}
4. Tính toán lần thứ i giá trị băm trung gian H(i):
=a+
=b+
=c+
=d+
=e+
=f+
=g+
=h+
}
Sau khi lặp đi lặp lại các bước 1 đến 4 N lần (tức là sau khi xử lý M (N)), thông
điệp tóm lược 256-bit của thông điệp M là:

24


CHƯƠNG IV : DEMO THUẬT TOÁN SHA-256 bằng PHP
1. Viết chương trình
Để làm được việc này, ta cần tạo một trang “sha256.php” có ch ứa các
hàm để băm dữ liệu nhập vào và đưa ra kết quả. Nội dung của file này nh ư
sau:

class Hash
{
function sha256($msg)
{
$msg = Hash::utf8Encode($msg);
$msg.= chr(128);
$l = ceil(strlen($msg) / 4) + 2;
$N = ceil($l / 16);
$M = array();
for ($i = 0; $i < $N; $i++)
{
$M[] = array();
for ($j = 0; $j < 16; $j ++)
{
$M[$i][] = (ord(substr($msg, $i * 64 + $j * 4, 1)) << 24) |
(ord(substr($msg, $i * 64 + $j * 4 + 1, 1)) << 16) |
(ord(substr($msg, $i * 64 + $j * 4 + 2, 1)) << 8) |
(ord(substr($msg, $i * 64 + $j * 4 + 3, 1)));
}
25