[Funland] Tranh cãi trên bàn nhậu , mời cc giải đáp

nhatlongcamera2

Xe tăng
Biển số
OF-84732
Ngày cấp bằng
10/2/11
Số km
1,059
Động cơ
12,704 Mã lực
A nói: nếu tóm bất kì 100 người ngoài đường thì tỉ lệ có 2 người trùng ngày sinh với nhau LỚN HƠN 50%
B bảo phải ít nhất 183 người mới được 50%
A hay B đúng? thua trả tiền nhậu cho 10ng
 

comiki

Xe lăn
Biển số
OF-504527
Ngày cấp bằng
13/4/17
Số km
11,705
Động cơ
42,458,730 Mã lực
367 người thì chắc 100%
 

Hoàng Trang

Xe ba gác
Biển số
OF-422667
Ngày cấp bằng
16/5/16
Số km
21,785
Động cơ
1,332,566 Mã lực
Nơi ở
Hà Nội
A nói: nếu tóm bất kì 100 người ngoài đường thì tỉ lệ có 2 người trùng ngày sinh với nhau LỚN HƠN 50%
B bảo phải ít nhất 183 người mới được 50%
A hay B đúng? thua trả tiền nhậu cho 10ng
A đúng cụ ạ. Cái này theo Nghịch lý ngày sinh. Chỉ cần túm 57 người ngẫu nhiên thì xác suất đã 99%.
 

matizvan2009

Xe lăn
Biển số
OF-42690
Ngày cấp bằng
8/8/09
Số km
14,988
Động cơ
-125,805 Mã lực
Đơn vị em làm việc có 3 người, em với 2 thằng em, 2 thằng cùng ngày sinh nhật.
 

matizvan2009

Xe lăn
Biển số
OF-42690
Ngày cấp bằng
8/8/09
Số km
14,988
Động cơ
-125,805 Mã lực
A đúng cụ ạ. Cái này theo Nghịch lý ngày sinh. Chỉ cần túm 57 người ngẫu nhiên thì xác suất đã 99%.
Mợ chắc nói chỉ về ngày, chủ thớt nói (chưa rõ nhưng) là ngày sinh nhật
 

zenious

Xe máy
Biển số
OF-83386
Ngày cấp bằng
20/1/11
Số km
77
Động cơ
21 Mã lực
Xác suất thống kê thôi cụ,tìm các cháu sv năm 1 giải
 

XPQ

Xe lăn
Biển số
OF-25733
Ngày cấp bằng
13/12/08
Số km
13,042
Động cơ
2,468,731 Mã lực
Nơi ở
Trỏng
A nói: nếu tóm bất kì 100 người ngoài đường thì tỉ lệ có 2 người trùng ngày sinh với nhau LỚN HƠN 50%
B bảo phải ít nhất 183 người mới được 50%
A hay B đúng? thua trả tiền nhậu cho 10ng
Trùng ngày sinh thì theo như em đã đọc đâu đó, đúng là cứ 100 đứa thì tỷ lệ có 2 đứa trùng ngày sinh lớn hơn 50%. Một tháng có 30-31 ngày và 100 đứa thì đại loại trung bình 3,3 đứa một ngày.
 

dtrung

Xe điện
Biển số
OF-8577
Ngày cấp bằng
20/8/07
Số km
2,629
Động cơ
56,444 Mã lực
Ngày sinh thì tính có 31 ngày thôi, từ 1 đến 31, nên xác xuất là 100/31 lớn hơn 50%
 

Of.NguyenLinh

Xe ngựa
{Kinh doanh chuyên nghiệp}
Người OF
Biển số
OF-291212
Ngày cấp bằng
6/6/06
Số km
28,348
Động cơ
-15,233,978 Mã lực
Nơi ở
Sản phẩm chăm sóc xe nextzett
Website
1z-vietnam.com

Khoa Béo

Xe buýt
Biển số
OF-84286
Ngày cấp bằng
4/2/11
Số km
723
Động cơ
-19,930,134 Mã lực
Uống xong ra đứng ở ngã tư phát phiếu cho 100 ng hả cụ?
 

Lỡ mà

Xe đạp
Biển số
OF-798325
Ngày cấp bằng
24/11/21
Số km
14
Động cơ
6,989,494 Mã lực
Tuổi
47
Có nhậu em vào xem :))
 

giradeo

Xe tải
Biển số
OF-297869
Ngày cấp bằng
8/11/13
Số km
369
Động cơ
19,594 Mã lực
Hình như xác suất này còn bị ảnh hưởng bởi chu kỳ của chị em?
 

Kem tươi

[Tịch thu bằng lái]
Biển số
OF-508190
Ngày cấp bằng
4/5/17
Số km
7,093
Động cơ
128,085 Mã lực
A nói: nếu tóm bất kì 100 người ngoài đường thì tỉ lệ có 2 người trùng ngày sinh với nhau LỚN HƠN 50%
B bảo phải ít nhất 183 người mới được 50%
A hay B đúng? thua trả tiền nhậu cho 10ng
Xác suất gần 100% mà, xem link này sẽ rõ.
(Thằng A đúng, thằng B chuẩn bị tiền nhậu đi là vừa :)) )



Tấn công Ngày sinh là một loại tấn công mật mã dựa trên sự khai thác vấn đề Ngày sinh(Birthday problem)- một hiện tượng xác suất tạo ra nghịch lý đối với cảm giác của con người, do vậy còn được gọi là “Nghịch lý Ngày sinh”(Birthday paradox).
Bài này phân tích và chứng minh hiện tượng nghịch lý trên cùng với mối liên hệ ứng dụng mật mã trong tấn công/phòng vệ tấn công. Cuối bài là một chương trình với mã nguồn thực thi, kèm theo các giải thích cần thiết. Kiến thức trong bài phần lớn là những kiến thức phổ thông cho nên các bạn sẽ hiểu được dễ dàng, chỉ cần tốt nghiệp phổ thông trung học(bằng thật, học thật). Bạn sẽ gặp thuận lợi đối với một vài chi tiết khác nếu bạn có trình độ tin học căn bản. Về phần chương trình thì bạn cần biết sơ qua về ngôn ngữ C++; sử dụng một hệ điều hành kiểu Linux có trình biên dịch gcc.
Bài này cũng là cơ sở cho các khái niệm có thể gặp trong các bài sau có liên quan đến các vấn đề bí mật thông tin, các thuật toán mật mã, thuật toán mật mã không an toàn, tấn công tiền ảnh, tấn công tiền ảnh thứ hai, tấn công xung đột mạnh, chiến lược tìm kiếm, kỹ thuật mật mã khóa công khai, thực hành mã hóa và giải mã thông tin, thực hành ký kỹ thuật số, thực hành xác minh chữ ký kỹ thuật số, thực hành xác nhận các chứng chỉ CA-Certificates và loại bỏ các chứng chỉ không hợp lệ.

Nếu bạn đang ở trong một nhóm người ngẫu nhiên trong một căn phòng với số người lớn hơn con số 23, bạn có thể cá cược với ai đó rằng có ít nhất một cặp hai người nào đó có trùng ngày sinh, và phần thắng sẽ nghiêng về bạn. Một năm không kể năm nhuận là có 365 ngày vì thế có 365 ngày sinh khác nhau, một con số lớn hơn nhiều so với 23 làm cho chúng ta có cảm giác đây là điều nghịch lý. Nhưng lý thuyết xác suất thống kê đã chỉ ra rằng với 23 người ngẫu nhiên thì xác suất có ít nhất hai người có trùng ngày sinh là 50%.
Gọi xác suất cần tính là P(A). Chúng ta giải bài toán ngược lại, tìm xác suất P(A’) để 23 người ngẫu nhiên có ngày sinh hoàn toàn khác nhau.
Vì mỗi một người đều có thể có ngày sinh là một ngày trong 365 ngày của năm nên số khả năng về tình trạng ngày sinh của 23 người sẽ là chỉnh hợp lặp chập 23 của 365 phần tử
birthday011
Số khả năng thuận lợi là số bộ 23 ngày sinh mà không có cặp hai ngày sinh nào trùng nhau, đây chính là chỉnh hợp(không lặp) chập 23 của 365 phần tử
birthday012
Vậy xác suất P(A’), từ đó xác suất P(A) sẽ bằng

Công thức tổng quát cho n người, xác suất p(n) để có ít nhất hai người trong n người ngẫu nhiên trùng ngày sinh sẽ là
birthday02 (*)
Để thử kết quả, bạn dùng một tiện ích tính toán. 365! là một số rất lớn, có đến 778 chữ số 0, một chương trình tính toán bình thường không tính được. Bạn chạy chương trình kcalc, vào menu Settings, chọn chế độ khoa học(Science Mode)
KCalc
Với n=70 chúng ta sẽ được kết quả p(70) xấp xỉ 99.9%. Như vậy, với 70 người ngẫu nhiên, hầu như chắc chắn có ít nhất hai người có ngày sinh giống nhau.
Tính toán xấp xỉ
Công thức (*) là công thức tính toán chính xác. Khi áp dụng vào mật mã, số ngày 365 ngày trong năm sẽ được thay thế bằng kích thước không gian mật mã, là số chuỗi nhị phân khác nhau với một độ dài chuỗi nhất định. Ví dụ với chuỗi nhị phân dài 32 bits, con số này là 2³², hơn 4 tỷ. Tính toán con số lớn như vậy sử dụng trực tiếp công thức (*) là không khả thi thực hành. Cho nên cần phương pháp xấp xỉ. Từ công thức (*), xác suất để n người ngẫu nhiên có ngày sinh hoàn toàn khác nhau là
birthday031 (**)

Khai triển Taylor áp dụng cho x tại lận cận điểm 0, |x| << 1
birthday032
Với x=-1/365
birthday041
Với x=-2/365
birthday042
Lặp lại tương tự cho đến x=-(n-1)/365
birthday043
Thay các giá trị gần đúng vế trái vào công thức (**)
birthday044
Từ đó chúng ta có công thức tính gần đúng xác suất p(n). Áp dụng vấn đề Ngày sinh vào các hiện tượng tương tự, “số ngày” không phải là 365 mà là một biến d. Với cách đặt vấn đề sử dụng khai triển Taylor nói trên khi đặt các giá trị x, phương pháp gần đúng này chỉ đạt độ chính xác với các x gần điểm 0, hay trị tuyệt đối của x nhỏ hơn 1 rất nhiều. Nói cách khác, khi n << d thì có thể áp dụng công thức
birthday051
Hàm xác suất(gần đúng) là một hàm theo “số người” n và “số ngày” d.
Để tính n theo p và d, chúng ta biến đổi công thức trên
birthday052(***)
Cùng ngày sinh như bạn(Same birthday as you)
Nếu bạn bước vào một phòng có ngẫu nhiên n người, xác suất q(n) để có một ai đó trong phòng có cùng ngày sinh với bạn là một dạng khác của vấn đề Ngày sinh- xác suất có ít nhất một ngày sinh trong n ngày sinh ngẫu nhiên trùng với một ngày sinh cho trước. Tổng số khả năng có thể xảy ra đối với n ngày sinh này vẫn là
birthday061
Chúng ta lại làm bài toán ngược: tìm xác suất để không có ai trong n người này có ngày sinh như bạn. Về số khả năng thuận lợi, vì mỗi người đều có thể có ngày sinh trong năm trừ ngày sinh của bạn nên số khả năng thuận lợi của bộ n ngày sinh này là chỉnh hợp lặp chập n của (365-1) phần tử, bằng
birthday062
Vậy
birthday063
Với n=23 thì tính ra q(n) khoảng 6.1%, nhỏ hơn p(n) tương ứng là 50% rất nhiều. Lý do là trong 23 người này có thể có một hoặc nhiều cặp trùng ngày sinh nhưng họ lại khó trùng ngày sinh với bạn. Cũng vì lý do này mà để xác suất q(n) đạt 50% thì số người n phải là 253 > 365/2.
Tổng quát cho d “ngày”, xác suất là một hàm theo “số người” và “số ngày”
birthday064
Bảng xác suất
��������
10−1810−1510−1210−910−60.1%1%25%50%75%

[TH]Số bits[/TH]
[TH]Cỡ không gian băm
(2Số bits)[/TH]
[TH]Xác suất xảy ra xung đột (p)[/TH]
[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]
[TD]16[/TD]
[TD]65,536[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]11[/TD]
[TD]36[/TD]
[TD]190[/TD]
[TD]300[/TD]
[TD]430[/TD]
[TD]32[/TD]
[TD]4.3 × 109[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]3[/TD]
[TD]93[/TD]
[TD]2900[/TD]
[TD]9300[/TD]
[TD]50,000[/TD]
[TD]77,000[/TD]
[TD]110,000[/TD]
[TD]64[/TD]
[TD]1.8 × 1019[/TD]
[TD]6[/TD]
[TD]190[/TD]
[TD]6100[/TD]
[TD]190,000[/TD]
[TD]6,100,000[/TD]
[TD]1.9 × 108[/TD]
[TD]6.1 × 108[/TD]
[TD]3.3 × 109[/TD]
[TD]5.1 × 109[/TD]
[TD]7.2 × 109[/TD]
[TD]128[/TD]
[TD]3.4 × 1038[/TD]
[TD]2.6 × 1010[/TD]
[TD]8.2 × 1011[/TD]
[TD]2.6 × 1013[/TD]
[TD]8.2 × 1014[/TD]
[TD]2.6 × 1016[/TD]
[TD]8.3 × 1017[/TD]
[TD]2.6 × 1018[/TD]
[TD]1.4 × 1019[/TD]
[TD]2.2 × 1019[/TD]
[TD]3.1 × 1019[/TD]
[TD]256[/TD]
[TD]1.2 × 1077[/TD]
[TD]4.8 × 1029[/TD]
[TD]1.5 × 1031[/TD]
[TD]4.8 × 1032[/TD]
[TD]1.5 × 1034[/TD]
[TD]4.8 × 1035[/TD]
[TD]1.5 × 1037[/TD]
[TD]4.8 × 1037[/TD]
[TD]2.6 × 1038[/TD]
[TD]4.0 × 1038[/TD]
[TD]5.7 × 1038[/TD]
[TD]384[/TD]
[TD]3.9 × 10115[/TD]
[TD]8.9 × 1048[/TD]
[TD]2.8 × 1050[/TD]
[TD]8.9 × 1051[/TD]
[TD]2.8 × 1053[/TD]
[TD]8.9 × 1054[/TD]
[TD]2.8 × 1056[/TD]
[TD]8.9 × 1056[/TD]
[TD]4.8 × 1057[/TD]
[TD]7.4 × 1057[/TD]
[TD]1.0 × 1058[/TD]
[TD]512[/TD]
[TD]1.3 × 10154[/TD]
[TD]1.6 × 1068[/TD]
[TD]5.2 × 1069[/TD]
[TD]1.6 × 1071[/TD]
[TD]5.2 × 1072[/TD]
[TD]1.6 × 1074[/TD]
[TD]5.2 × 1075[/TD]
[TD]1.6 × 1076[/TD]
[TD]8.8 × 1076[/TD]
[TD]1.4 × 1077[/TD]
[TD]1.9 × 1077[/TD]​

Đây là bảng xác suất mật mã đưa ra các giá trị khung. Các ô màu trắng biểu thị số lượng giá trị băm( hashes) cần thiết để tấn công phá vỡ kháng xung đột mạnh với xác suất tương ứng theo cột và kích thước không gian băm theo hàng. “Kích thước không gian băm” ứng với “số ngày d”, “xác suất xung đột” ứng với “xác suất trùng ngày sinh”, và “số băm cần thiết” ứng với “số người n”.

Chương trình
Chương trình áp dụng công thức (***) để tính số băm cho các trường hợp xác suất nhỏ. Đối với các xác suất lớn xa điểm 0 thì công thức xấp xỉ sẽ gặp sai số, khi đó một hàm nội suy đa thức cho các giá trị khung trong bảng xác suất bên trên sẽ được sử dụng thay thế. Đó là hàm LookAyken.
 
Chỉnh sửa cuối:

dongnat123

Xe container
Biển số
OF-477830
Ngày cấp bằng
19/12/16
Số km
6,879
Động cơ
425,486 Mã lực
Em vào hóng đoạn múa võ hậu tránh cãi :D
 

Kem tươi

[Tịch thu bằng lái]
Biển số
OF-508190
Ngày cấp bằng
4/5/17
Số km
7,093
Động cơ
128,085 Mã lực
Em vào hóng đoạn múa võ hậu tránh cãi :D
B thua phải trả tiền nhậu, A thắng lại vốn đang có men say nên buông lời "DCM Thằng B thế mà dốt toán chắc hồi bé toàn trốn học"

Và kết cục: :D

 

Abcdefghiklmnkl

Xe đạp
Biển số
OF-782999
Ngày cấp bằng
8/7/21
Số km
45
Động cơ
545 Mã lực
Tuổi
111
Xác suất gần 100% mà, xem link này sẽ rõ.
(Thằng A đúng, thằng B chuẩn bị tiền nhậu đi là vừa :)) )



Tấn công Ngày sinh là một loại tấn công mật mã dựa trên sự khai thác vấn đề Ngày sinh(Birthday problem)- một hiện tượng xác suất tạo ra nghịch lý đối với cảm giác của con người, do vậy còn được gọi là “Nghịch lý Ngày sinh”(Birthday paradox).
Bài này phân tích và chứng minh hiện tượng nghịch lý trên cùng với mối liên hệ ứng dụng mật mã trong tấn công/phòng vệ tấn công. Cuối bài là một chương trình với mã nguồn thực thi, kèm theo các giải thích cần thiết. Kiến thức trong bài phần lớn là những kiến thức phổ thông cho nên các bạn sẽ hiểu được dễ dàng, chỉ cần tốt nghiệp phổ thông trung học(bằng thật, học thật). Bạn sẽ gặp thuận lợi đối với một vài chi tiết khác nếu bạn có trình độ tin học căn bản. Về phần chương trình thì bạn cần biết sơ qua về ngôn ngữ C++; sử dụng một hệ điều hành kiểu Linux có trình biên dịch gcc.
Bài này cũng là cơ sở cho các khái niệm có thể gặp trong các bài sau có liên quan đến các vấn đề bí mật thông tin, các thuật toán mật mã, thuật toán mật mã không an toàn, tấn công tiền ảnh, tấn công tiền ảnh thứ hai, tấn công xung đột mạnh, chiến lược tìm kiếm, kỹ thuật mật mã khóa công khai, thực hành mã hóa và giải mã thông tin, thực hành ký kỹ thuật số, thực hành xác minh chữ ký kỹ thuật số, thực hành xác nhận các chứng chỉ CA-Certificates và loại bỏ các chứng chỉ không hợp lệ.

Nếu bạn đang ở trong một nhóm người ngẫu nhiên trong một căn phòng với số người lớn hơn con số 23, bạn có thể cá cược với ai đó rằng có ít nhất một cặp hai người nào đó có trùng ngày sinh, và phần thắng sẽ nghiêng về bạn. Một năm không kể năm nhuận là có 365 ngày vì thế có 365 ngày sinh khác nhau, một con số lớn hơn nhiều so với 23 làm cho chúng ta có cảm giác đây là điều nghịch lý. Nhưng lý thuyết xác suất thống kê đã chỉ ra rằng với 23 người ngẫu nhiên thì xác suất có ít nhất hai người có trùng ngày sinh là 50%.
Gọi xác suất cần tính là P(A). Chúng ta giải bài toán ngược lại, tìm xác suất P(A’) để 23 người ngẫu nhiên có ngày sinh hoàn toàn khác nhau.
Vì mỗi một người đều có thể có ngày sinh là một ngày trong 365 ngày của năm nên số khả năng về tình trạng ngày sinh của 23 người sẽ là chỉnh hợp lặp chập 23 của 365 phần tử
birthday011
Số khả năng thuận lợi là số bộ 23 ngày sinh mà không có cặp hai ngày sinh nào trùng nhau, đây chính là chỉnh hợp(không lặp) chập 23 của 365 phần tử
birthday012
Vậy xác suất P(A’), từ đó xác suất P(A) sẽ bằng

Công thức tổng quát cho n người, xác suất p(n) để có ít nhất hai người trong n người ngẫu nhiên trùng ngày sinh sẽ là
birthday02 (*)
Để thử kết quả, bạn dùng một tiện ích tính toán. 365! là một số rất lớn, có đến 778 chữ số 0, một chương trình tính toán bình thường không tính được. Bạn chạy chương trình kcalc, vào menu Settings, chọn chế độ khoa học(Science Mode)
KCalc
Với n=70 chúng ta sẽ được kết quả p(70) xấp xỉ 99.9%. Như vậy, với 70 người ngẫu nhiên, hầu như chắc chắn có ít nhất hai người có ngày sinh giống nhau.
Tính toán xấp xỉ
Công thức (*) là công thức tính toán chính xác. Khi áp dụng vào mật mã, số ngày 365 ngày trong năm sẽ được thay thế bằng kích thước không gian mật mã, là số chuỗi nhị phân khác nhau với một độ dài chuỗi nhất định. Ví dụ với chuỗi nhị phân dài 32 bits, con số này là 2³², hơn 4 tỷ. Tính toán con số lớn như vậy sử dụng trực tiếp công thức (*) là không khả thi thực hành. Cho nên cần phương pháp xấp xỉ. Từ công thức (*), xác suất để n người ngẫu nhiên có ngày sinh hoàn toàn khác nhau là
birthday031 (**)

Khai triển Taylor áp dụng cho x tại lận cận điểm 0, |x| << 1
birthday032
Với x=-1/365
birthday041
Với x=-2/365
birthday042
Lặp lại tương tự cho đến x=-(n-1)/365
birthday043
Thay các giá trị gần đúng vế trái vào công thức (**)
birthday044
Từ đó chúng ta có công thức tính gần đúng xác suất p(n). Áp dụng vấn đề Ngày sinh vào các hiện tượng tương tự, “số ngày” không phải là 365 mà là một biến d. Với cách đặt vấn đề sử dụng khai triển Taylor nói trên khi đặt các giá trị x, phương pháp gần đúng này chỉ đạt độ chính xác với các x gần điểm 0, hay trị tuyệt đối của x nhỏ hơn 1 rất nhiều. Nói cách khác, khi n << d thì có thể áp dụng công thức
birthday051
Hàm xác suất(gần đúng) là một hàm theo “số người” n và “số ngày” d.
Để tính n theo p và d, chúng ta biến đổi công thức trên
birthday052(***)
Cùng ngày sinh như bạn(Same birthday as you)
Nếu bạn bước vào một phòng có ngẫu nhiên n người, xác suất q(n) để có một ai đó trong phòng có cùng ngày sinh với bạn là một dạng khác của vấn đề Ngày sinh- xác suất có ít nhất một ngày sinh trong n ngày sinh ngẫu nhiên trùng với một ngày sinh cho trước. Tổng số khả năng có thể xảy ra đối với n ngày sinh này vẫn là
birthday061
Chúng ta lại làm bài toán ngược: tìm xác suất để không có ai trong n người này có ngày sinh như bạn. Về số khả năng thuận lợi, vì mỗi người đều có thể có ngày sinh trong năm trừ ngày sinh của bạn nên số khả năng thuận lợi của bộ n ngày sinh này là chỉnh hợp lặp chập n của (365-1) phần tử, bằng
birthday062
Vậy
birthday063
Với n=23 thì tính ra q(n) khoảng 6.1%, nhỏ hơn p(n) tương ứng là 50% rất nhiều. Lý do là trong 23 người này có thể có một hoặc nhiều cặp trùng ngày sinh nhưng họ lại khó trùng ngày sinh với bạn. Cũng vì lý do này mà để xác suất q(n) đạt 50% thì số người n phải là 253 > 365/2.
Tổng quát cho d “ngày”, xác suất là một hàm theo “số người” và “số ngày”
birthday064
Bảng xác suất
��������
10−1810−1510−1210−910−60.1%1%25%50%75%
[TH]Số bits[/TH]
[TH]Cỡ không gian băm
(2Số bits)[/TH]
[TH]Xác suất xảy ra xung đột (p)[/TH]
[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]
[TD]16[/TD]
[TD]65,536[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]11[/TD]
[TD]36[/TD]
[TD]190[/TD]
[TD]300[/TD]
[TD]430[/TD]
[TD]32[/TD]
[TD]4.3 × 109[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]3[/TD]
[TD]93[/TD]
[TD]2900[/TD]
[TD]9300[/TD]
[TD]50,000[/TD]
[TD]77,000[/TD]
[TD]110,000[/TD]
[TD]64[/TD]
[TD]1.8 × 1019[/TD]
[TD]6[/TD]
[TD]190[/TD]
[TD]6100[/TD]
[TD]190,000[/TD]
[TD]6,100,000[/TD]
[TD]1.9 × 108[/TD]
[TD]6.1 × 108[/TD]
[TD]3.3 × 109[/TD]
[TD]5.1 × 109[/TD]
[TD]7.2 × 109[/TD]
[TD]128[/TD]
[TD]3.4 × 1038[/TD]
[TD]2.6 × 1010[/TD]
[TD]8.2 × 1011[/TD]
[TD]2.6 × 1013[/TD]
[TD]8.2 × 1014[/TD]
[TD]2.6 × 1016[/TD]
[TD]8.3 × 1017[/TD]
[TD]2.6 × 1018[/TD]
[TD]1.4 × 1019[/TD]
[TD]2.2 × 1019[/TD]
[TD]3.1 × 1019[/TD]
[TD]256[/TD]
[TD]1.2 × 1077[/TD]
[TD]4.8 × 1029[/TD]
[TD]1.5 × 1031[/TD]
[TD]4.8 × 1032[/TD]
[TD]1.5 × 1034[/TD]
[TD]4.8 × 1035[/TD]
[TD]1.5 × 1037[/TD]
[TD]4.8 × 1037[/TD]
[TD]2.6 × 1038[/TD]
[TD]4.0 × 1038[/TD]
[TD]5.7 × 1038[/TD]
[TD]384[/TD]
[TD]3.9 × 10115[/TD]
[TD]8.9 × 1048[/TD]
[TD]2.8 × 1050[/TD]
[TD]8.9 × 1051[/TD]
[TD]2.8 × 1053[/TD]
[TD]8.9 × 1054[/TD]
[TD]2.8 × 1056[/TD]
[TD]8.9 × 1056[/TD]
[TD]4.8 × 1057[/TD]
[TD]7.4 × 1057[/TD]
[TD]1.0 × 1058[/TD]
[TD]512[/TD]
[TD]1.3 × 10154[/TD]
[TD]1.6 × 1068[/TD]
[TD]5.2 × 1069[/TD]
[TD]1.6 × 1071[/TD]
[TD]5.2 × 1072[/TD]
[TD]1.6 × 1074[/TD]
[TD]5.2 × 1075[/TD]
[TD]1.6 × 1076[/TD]
[TD]8.8 × 1076[/TD]
[TD]1.4 × 1077[/TD]
[TD]1.9 × 1077[/TD]​

Đây là bảng xác suất mật mã đưa ra các giá trị khung. Các ô màu trắng biểu thị số lượng giá trị băm( hashes) cần thiết để tấn công phá vỡ kháng xung đột mạnh với xác suất tương ứng theo cột và kích thước không gian băm theo hàng. “Kích thước không gian băm” ứng với “số ngày d”, “xác suất xung đột” ứng với “xác suất trùng ngày sinh”, và “số băm cần thiết” ứng với “số người n”.

Chương trình
Chương trình áp dụng công thức (***) để tính số băm cho các trường hợp xác suất nhỏ. Đối với các xác suất lớn xa điểm 0 thì công thức xấp xỉ sẽ gặp sai số, khi đó một hàm nội suy đa thức cho các giá trị khung trong bảng xác suất bên trên sẽ được sử dụng thay thế. Đó là hàm LookAyken.
Cụ ngồi ngay ngắn để em lạy!
 

matizvan2009

Xe lăn
Biển số
OF-42690
Ngày cấp bằng
8/8/09
Số km
14,988
Động cơ
-125,805 Mã lực
Xác suất gần 100% mà, xem link này sẽ rõ.
(Thằng A đúng, thằng B chuẩn bị tiền nhậu đi là vừa :)) )



Tấn công Ngày sinh là một loại tấn công mật mã dựa trên sự khai thác vấn đề Ngày sinh(Birthday problem)- một hiện tượng xác suất tạo ra nghịch lý đối với cảm giác của con người, do vậy còn được gọi là “Nghịch lý Ngày sinh”(Birthday paradox).
Bài này phân tích và chứng minh hiện tượng nghịch lý trên cùng với mối liên hệ ứng dụng mật mã trong tấn công/phòng vệ tấn công. Cuối bài là một chương trình với mã nguồn thực thi, kèm theo các giải thích cần thiết. Kiến thức trong bài phần lớn là những kiến thức phổ thông cho nên các bạn sẽ hiểu được dễ dàng, chỉ cần tốt nghiệp phổ thông trung học(bằng thật, học thật). Bạn sẽ gặp thuận lợi đối với một vài chi tiết khác nếu bạn có trình độ tin học căn bản. Về phần chương trình thì bạn cần biết sơ qua về ngôn ngữ C++; sử dụng một hệ điều hành kiểu Linux có trình biên dịch gcc.
Bài này cũng là cơ sở cho các khái niệm có thể gặp trong các bài sau có liên quan đến các vấn đề bí mật thông tin, các thuật toán mật mã, thuật toán mật mã không an toàn, tấn công tiền ảnh, tấn công tiền ảnh thứ hai, tấn công xung đột mạnh, chiến lược tìm kiếm, kỹ thuật mật mã khóa công khai, thực hành mã hóa và giải mã thông tin, thực hành ký kỹ thuật số, thực hành xác minh chữ ký kỹ thuật số, thực hành xác nhận các chứng chỉ CA-Certificates và loại bỏ các chứng chỉ không hợp lệ.

Nếu bạn đang ở trong một nhóm người ngẫu nhiên trong một căn phòng với số người lớn hơn con số 23, bạn có thể cá cược với ai đó rằng có ít nhất một cặp hai người nào đó có trùng ngày sinh, và phần thắng sẽ nghiêng về bạn. Một năm không kể năm nhuận là có 365 ngày vì thế có 365 ngày sinh khác nhau, một con số lớn hơn nhiều so với 23 làm cho chúng ta có cảm giác đây là điều nghịch lý. Nhưng lý thuyết xác suất thống kê đã chỉ ra rằng với 23 người ngẫu nhiên thì xác suất có ít nhất hai người có trùng ngày sinh là 50%.
Gọi xác suất cần tính là P(A). Chúng ta giải bài toán ngược lại, tìm xác suất P(A’) để 23 người ngẫu nhiên có ngày sinh hoàn toàn khác nhau.
Vì mỗi một người đều có thể có ngày sinh là một ngày trong 365 ngày của năm nên số khả năng về tình trạng ngày sinh của 23 người sẽ là chỉnh hợp lặp chập 23 của 365 phần tử
birthday011
Số khả năng thuận lợi là số bộ 23 ngày sinh mà không có cặp hai ngày sinh nào trùng nhau, đây chính là chỉnh hợp(không lặp) chập 23 của 365 phần tử
birthday012
Vậy xác suất P(A’), từ đó xác suất P(A) sẽ bằng

Công thức tổng quát cho n người, xác suất p(n) để có ít nhất hai người trong n người ngẫu nhiên trùng ngày sinh sẽ là
birthday02 (*)
Để thử kết quả, bạn dùng một tiện ích tính toán. 365! là một số rất lớn, có đến 778 chữ số 0, một chương trình tính toán bình thường không tính được. Bạn chạy chương trình kcalc, vào menu Settings, chọn chế độ khoa học(Science Mode)
KCalc
Với n=70 chúng ta sẽ được kết quả p(70) xấp xỉ 99.9%. Như vậy, với 70 người ngẫu nhiên, hầu như chắc chắn có ít nhất hai người có ngày sinh giống nhau.
Tính toán xấp xỉ
Công thức (*) là công thức tính toán chính xác. Khi áp dụng vào mật mã, số ngày 365 ngày trong năm sẽ được thay thế bằng kích thước không gian mật mã, là số chuỗi nhị phân khác nhau với một độ dài chuỗi nhất định. Ví dụ với chuỗi nhị phân dài 32 bits, con số này là 2³², hơn 4 tỷ. Tính toán con số lớn như vậy sử dụng trực tiếp công thức (*) là không khả thi thực hành. Cho nên cần phương pháp xấp xỉ. Từ công thức (*), xác suất để n người ngẫu nhiên có ngày sinh hoàn toàn khác nhau là
birthday031 (**)

Khai triển Taylor áp dụng cho x tại lận cận điểm 0, |x| << 1
birthday032
Với x=-1/365
birthday041
Với x=-2/365
birthday042
Lặp lại tương tự cho đến x=-(n-1)/365
birthday043
Thay các giá trị gần đúng vế trái vào công thức (**)
birthday044
Từ đó chúng ta có công thức tính gần đúng xác suất p(n). Áp dụng vấn đề Ngày sinh vào các hiện tượng tương tự, “số ngày” không phải là 365 mà là một biến d. Với cách đặt vấn đề sử dụng khai triển Taylor nói trên khi đặt các giá trị x, phương pháp gần đúng này chỉ đạt độ chính xác với các x gần điểm 0, hay trị tuyệt đối của x nhỏ hơn 1 rất nhiều. Nói cách khác, khi n << d thì có thể áp dụng công thức
birthday051
Hàm xác suất(gần đúng) là một hàm theo “số người” n và “số ngày” d.
Để tính n theo p và d, chúng ta biến đổi công thức trên
birthday052(***)
Cùng ngày sinh như bạn(Same birthday as you)
Nếu bạn bước vào một phòng có ngẫu nhiên n người, xác suất q(n) để có một ai đó trong phòng có cùng ngày sinh với bạn là một dạng khác của vấn đề Ngày sinh- xác suất có ít nhất một ngày sinh trong n ngày sinh ngẫu nhiên trùng với một ngày sinh cho trước. Tổng số khả năng có thể xảy ra đối với n ngày sinh này vẫn là
birthday061
Chúng ta lại làm bài toán ngược: tìm xác suất để không có ai trong n người này có ngày sinh như bạn. Về số khả năng thuận lợi, vì mỗi người đều có thể có ngày sinh trong năm trừ ngày sinh của bạn nên số khả năng thuận lợi của bộ n ngày sinh này là chỉnh hợp lặp chập n của (365-1) phần tử, bằng
birthday062
Vậy
birthday063
Với n=23 thì tính ra q(n) khoảng 6.1%, nhỏ hơn p(n) tương ứng là 50% rất nhiều. Lý do là trong 23 người này có thể có một hoặc nhiều cặp trùng ngày sinh nhưng họ lại khó trùng ngày sinh với bạn. Cũng vì lý do này mà để xác suất q(n) đạt 50% thì số người n phải là 253 > 365/2.
Tổng quát cho d “ngày”, xác suất là một hàm theo “số người” và “số ngày”
birthday064
Bảng xác suất
��������
10−1810−1510−1210−910−60.1%1%25%50%75%
[TH]Số bits[/TH]
[TH]Cỡ không gian băm
(2Số bits)[/TH]
[TH]Xác suất xảy ra xung đột (p)[/TH]
[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]

[TH][/TH]
[TD]16[/TD]
[TD]65,536[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]11[/TD]
[TD]36[/TD]
[TD]190[/TD]
[TD]300[/TD]
[TD]430[/TD]
[TD]32[/TD]
[TD]4.3 × 109[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]<2[/TD]
[TD]3[/TD]
[TD]93[/TD]
[TD]2900[/TD]
[TD]9300[/TD]
[TD]50,000[/TD]
[TD]77,000[/TD]
[TD]110,000[/TD]
[TD]64[/TD]
[TD]1.8 × 1019[/TD]
[TD]6[/TD]
[TD]190[/TD]
[TD]6100[/TD]
[TD]190,000[/TD]
[TD]6,100,000[/TD]
[TD]1.9 × 108[/TD]
[TD]6.1 × 108[/TD]
[TD]3.3 × 109[/TD]
[TD]5.1 × 109[/TD]
[TD]7.2 × 109[/TD]
[TD]128[/TD]
[TD]3.4 × 1038[/TD]
[TD]2.6 × 1010[/TD]
[TD]8.2 × 1011[/TD]
[TD]2.6 × 1013[/TD]
[TD]8.2 × 1014[/TD]
[TD]2.6 × 1016[/TD]
[TD]8.3 × 1017[/TD]
[TD]2.6 × 1018[/TD]
[TD]1.4 × 1019[/TD]
[TD]2.2 × 1019[/TD]
[TD]3.1 × 1019[/TD]
[TD]256[/TD]
[TD]1.2 × 1077[/TD]
[TD]4.8 × 1029[/TD]
[TD]1.5 × 1031[/TD]
[TD]4.8 × 1032[/TD]
[TD]1.5 × 1034[/TD]
[TD]4.8 × 1035[/TD]
[TD]1.5 × 1037[/TD]
[TD]4.8 × 1037[/TD]
[TD]2.6 × 1038[/TD]
[TD]4.0 × 1038[/TD]
[TD]5.7 × 1038[/TD]
[TD]384[/TD]
[TD]3.9 × 10115[/TD]
[TD]8.9 × 1048[/TD]
[TD]2.8 × 1050[/TD]
[TD]8.9 × 1051[/TD]
[TD]2.8 × 1053[/TD]
[TD]8.9 × 1054[/TD]
[TD]2.8 × 1056[/TD]
[TD]8.9 × 1056[/TD]
[TD]4.8 × 1057[/TD]
[TD]7.4 × 1057[/TD]
[TD]1.0 × 1058[/TD]
[TD]512[/TD]
[TD]1.3 × 10154[/TD]
[TD]1.6 × 1068[/TD]
[TD]5.2 × 1069[/TD]
[TD]1.6 × 1071[/TD]
[TD]5.2 × 1072[/TD]
[TD]1.6 × 1074[/TD]
[TD]5.2 × 1075[/TD]
[TD]1.6 × 1076[/TD]
[TD]8.8 × 1076[/TD]
[TD]1.4 × 1077[/TD]
[TD]1.9 × 1077[/TD]​

Đây là bảng xác suất mật mã đưa ra các giá trị khung. Các ô màu trắng biểu thị số lượng giá trị băm( hashes) cần thiết để tấn công phá vỡ kháng xung đột mạnh với xác suất tương ứng theo cột và kích thước không gian băm theo hàng. “Kích thước không gian băm” ứng với “số ngày d”, “xác suất xung đột” ứng với “xác suất trùng ngày sinh”, và “số băm cần thiết” ứng với “số người n”.

Chương trình
Chương trình áp dụng công thức (***) để tính số băm cho các trường hợp xác suất nhỏ. Đối với các xác suất lớn xa điểm 0 thì công thức xấp xỉ sẽ gặp sai số, khi đó một hàm nội suy đa thức cho các giá trị khung trong bảng xác suất bên trên sẽ được sử dụng thay thế. Đó là hàm LookAyken.
đấy, các cụ cứ phàn nàn học toán làm gì đi.
em kết luận: học toán để nhậu chùa.
 
Thông tin thớt
Đang tải

Bài viết mới

Top