banner

[Rule] Rules  [Home] Main Forum  [Portal] Portal  
[Members] Member Listing  [Statistics] Statistics  [Search] Search  [Reading Room] Reading Room 
[Register] Register  
[Login] Loginhttp  | https  ]
 
Forum Index Thảo luận hệ điều hành Windows Hỏi về toán tử "^" (XOR)  XML
  [Programming]   Hỏi về toán tử "^" (XOR) 03/11/2007 22:48:19 (+0700) | #1 | 95095
[Avatar]
zThienLongz
Member

[Minus]    0    [Plus]
Joined: 29/08/2006 10:09:05
Messages: 104
Location: World
Offline
[Profile] [PM] [WWW]
Mình đọc được 1 cuốn tối ưu thuật đoạn mã thấy có viết xài toán tử XOR trong việc hoán vị 2 số
đoạn mã như sau:
void hoanvi(int &a,int &b){
a=a^b;
b=a^b;
a=a^b;


Bạn nào có thể giải thích cụ thể cho mình chi tiết về đoạn mã kia với. Giả sử khi minh nhập số a=5 và số b=6 thì trong dòng lênh thứ nhất a=a^b; nó cho bằng 1 số bất kì là 3 chẳng hạn . Mình muốn hỏi rằng: làm sao ta biết đc trong dòng lệnh thứ nhất a bằng bao nhiu (tức là biết đc chính xác số bất kì kia sẽ là bao nhiu)
Tiếp đến là dòng lệnh thứ 2 b=a^b; trong câu lệnh này b sẽ được gán giá trị 5 nhưng 1 vấn đề mình tự hỏi là tại sao lại là con số 5 mà không là con số khác vì dòng lệnh thứ 2 và thứ 1 là khá giống nhau vế phải dều là a^b chỉ khác 1 cái là a=5 và 1 cái a=3 . Tại sao không cho ra 1 con số bất kì như dòng lệnh 1.
Tiếp theo dòng lệnh thứ 3 tương tự như dòng lệnh thứ 2 a được gán giá trị 6
Mọi người hãy giải thích giúp mình với. Thanks
[Up] [Print Copy]
  [Question]   Hỏi về toán tử "^" (XOR) 03/11/2007 23:41:24 (+0700) | #2 | 95108
facialz
Elite Member

[Minus]    0    [Plus]
Joined: 20/07/2004 03:48:17
Messages: 197
Location: HoChiMinh city
Offline
[Profile] [PM]

zThienLongz wrote:
Mình đọc được 1 cuốn tối ưu thuật đoạn mã thấy có viết xài toán tử XOR trong việc hoán vị 2 số
đoạn mã như sau:
Code:
void hoanvi(int &a,int &b){
    a=a^b;
    b=a^b;
    a=a^b;
}


Bạn nào có thể giải thích cụ thể cho mình chi tiết về đoạn mã kia với. 


Gọi giá trị ban đầu của a, b là a(0), b(0). Nếu trước một lệnh gán a =...., giá trị của a là a(k) thì gọi giá trị của a sau lệnh gán ấy là a(k+1).

// a == a(0)
// b == b(0)

Giá trị của a, b qua chuỗi lệnh là
Code:
a=a^b;  // a(1) == a(0) ^ b(0)
b=a^b;  // b(1) == a(1) ^ b(0) == a(0) ^ b(0) ^ b(0) == a(0)
a=a^b;  // a(2) == a(1) ^ b(1) == a(0) ^ b(0) ^ a(0) == b(0)


Kết quả cuối cùng là
// a == a(2) == b(0)
// b == b(1) == a(0)
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 04/11/2007 02:28:53 (+0700) | #3 | 95140
FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline
[Profile] [PM]
Code:
(a^b)^b = a


- Đây là 1 cách mã hóa + giải mãcổ xưa.
- Để hiểu rõ hơn bạn xem phép XOR trên các bit:
Code:
0^0=0
    0^1=1
    1^0=1
    1^1=0


FaL
Hãy giữ một trái tim nóng và một cái đầu lạnh
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 04/11/2007 09:41:20 (+0700) | #4 | 95231
Mr.Khoai
Moderator

Joined: 27/06/2006 01:55:07
Messages: 954
Offline
[Profile] [PM]
Hi FaL,

Cái a=(a^x)^x đâu có mã hóa gì. Đó đơn giản là một tính chất của toán tử XOR mà thôi. Cách "swap" hai toán tử kiểu này chỉ dùng khi nào mình thật sự thiếu hụt registers hoặc để tiết kiệm bộ nhớ.

khoai
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 04/11/2007 11:05:19 (+0700) | #5 | 95244
FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline
[Profile] [PM]
Hi Khoai,

- Chả là FaL vừa làm 1 bài tập có liên quan đến phép toán này.
- Nó là thế này:

Mã hóa 1 sentence bằng 1 key cho trước bằng cách lấy sentence[i]^key[j] (các ký tự của key được dùng lặp lại kiểu circle).

Sau đó là bài:

Tìm key khi biết sentence và encrypted sentece

Một cách mã hóa cổ xửa là vì thế.

FaL.
Hãy giữ một trái tim nóng và một cái đầu lạnh
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 05/11/2007 00:18:37 (+0700) | #6 | 95321
Mr.Khoai
Moderator

Joined: 27/06/2006 01:55:07
Messages: 954
Offline
[Profile] [PM]
Chính xác thì mình phải nói là có một số thuật toán áp dụng XOR vì đó là một trong các toán tử căn bản, và rất nhanh. Nhưng nếu mã hóa kiểm C = P xor K thì không an toàn chút nào. Thường thì XOR chỉ là một trong số một số toán tử dùng để mã hóa.

khoai
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 05/11/2007 09:26:34 (+0700) | #7 | 95411
[Avatar]
zThienLongz
Member

[Minus]    0    [Plus]
Joined: 29/08/2006 10:09:05
Messages: 104
Location: World
Offline
[Profile] [PM] [WWW]
hix mọi người tranh luận sôi nổi quá. hì hì.......
Thực ra thì toán tử XOR trên bit thì mình biết rồi còn với số thực thì nó tườn đương với phép trừ
vd:
c=a^b;
tương đương với c=a-b;
Khoai có thể nói rõ hơn là tại sao không an toàn không vì mình thấy xài nó rất nhanh, thích hợp tối ưu đoạn mã
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 05/11/2007 14:40:28 (+0700) | #8 | 95455
[Avatar]
alice
Elite Member

[Minus]    0    [Plus]
Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline
[Profile] [PM]
Hi zThienLongz,

Mr.Khoai đang nói đến "mã hóa" chứ không nói đến "tối ưu đoạn mã" của bạn.

XOR không an toàn vì biết P, C cho phép tính được K dễ dàng.
Như hà nghịch lỗ lai xâm phạm
如 何 逆 虜 來 侵 犯
[Up] [Print Copy]
  [Question]   Hỏi về toán tử "^" (XOR) 05/11/2007 17:54:15 (+0700) | #9 | 95464
FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline
[Profile] [PM]
Chết thật, FaL không đọc đọc kỹ entry đầu tiên, nên những entry sau có vẻ nó đi xa vấn đề quá. Quay trở lại câu hỏi của zThienLongz:

zThienLongz wrote:
Mình đọc được 1 cuốn tối ưu thuật đoạn mã thấy có viết xài toán tử XOR trong việc hoán vị 2 số
đoạn mã như sau:
void hoanvi(int &a,int &b){
a=a^b;
b=a^b;
a=a^b;


Bạn nào có thể giải thích cụ thể cho mình chi tiết về đoạn mã kia với. Giả sử khi minh nhập số a=5 và số b=6 thì trong dòng lênh thứ nhất a=a^b; nó cho bằng 1 số bất kì là 3 chẳng hạn -1-. Mình muốn hỏi rằng: làm sao ta biết đc trong dòng lệnh thứ nhất a bằng bao nhiu -2-(tức là biết đc chính xác số bất kì kia sẽ là bao nhiu) 


-1- Ở đây không thể là một số bất kỳ được, nếu a = 5, b = 6, thì a ^ b = 3. Bạn kiểm tra lại phép này cụ thể trên các bit sẽ thấy được kết quả.

-2-
Muốn biết bằng bao nhiêu tất nhiên là phải thực hiện phép tính rồi! smilie


zThienLongz wrote:

Tiếp đến là dòng lệnh thứ 2 b=a^b; trong câu lệnh này b sẽ được gán giá trị 5 nhưng 1 vấn đề mình tự hỏi là tại sao lại là con số 5 mà không là con số khác vì dòng lệnh thứ 2 và thứ 1 là khá giống nhau vế phải dều là a^b chỉ khác 1 cái là a=5 và 1 cái a=3 . Tại sao không cho ra 1 con số bất kì như dòng lệnh 1.
Tiếp theo dòng lệnh thứ 3 tương tự như dòng lệnh thứ 2 a được gán giá trị 6
Mọi người hãy giải thích giúp mình với. Thanks 


- Tất nhiên là không ra số bất kỳ rồi, câu trả lời của phần này nằm ở các bài trên.

FaL

(Chà FaL trả lời tốt quá! smilie )
Hãy giữ một trái tim nóng và một cái đầu lạnh
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 06/11/2007 05:01:30 (+0700) | #10 | 95563
[Avatar]
zThienLongz
Member

[Minus]    0    [Plus]
Joined: 29/08/2006 10:09:05
Messages: 104
Location: World
Offline
[Profile] [PM] [WWW]
Uh` cám ơn FAL mình kiểm tra lại rồi đúng lại rồi
ta đổi 2 số a và b sang số nhị phân thì được là a=101 còn b=110 . Khi đó
a^b==101^110==011 và chuyển sang hệ dec (hệ số đếm 10) thì bằng 3
Nhưng còn về phần mã hóa thì sao lại nói là nguy hiểm đúng là khi viết C=P^K , nếu ta biết đc C, P thì tính đc K dễ dàng nhưng có gì là nguy hiểm đâu
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 06/11/2007 05:31:39 (+0700) | #11 | 95570
FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline
[Profile] [PM]

zThienLongz wrote:
Uh` cám ơn FAL mình kiểm tra lại rồi đúng lại rồi
ta đổi 2 số a và b sang số nhị phân thì được là a=101 còn b=110 . Khi đó
a^b==101^110==011 và chuyển sang hệ dec (hệ số đếm 10) thì bằng 3
Nhưng còn về phần mã hóa thì sao lại nói là nguy hiểm đúng là khi viết C=P^K , nếu ta biết đc C, P thì tính đc K dễ dàng nhưng có gì là nguy hiểm đâu 


+ Hì, đổi ra như thế là gần đúng thôi, phải là 00000101 và 00000110 mới đúng smilie.

+ Còn vụ nguy hiểm thì thật ra nói: RẤT NGUY HIỂM mới đúng. Không tin cậu làm cái bài tớ post trên kia thì biết.

FaL.

Hãy giữ một trái tim nóng và một cái đầu lạnh
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 06/11/2007 10:13:20 (+0700) | #12 | 95605
[Avatar]
gsmth
Elite Member

[Minus]    0    [Plus]
Joined: 15/02/2007 13:25:36
Messages: 749
Offline
[Profile] [PM] [WWW] [Yahoo!]
Nếu P(Plaintext), K(Key) được giữ bí mật và áp dụng http://world.std.com/~franl/crypto/one-time-pad.html.
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 06/11/2007 11:09:01 (+0700) | #13 | 95610
FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline
[Profile] [PM]

gsmth wrote:
Nếu P(Plaintext), K(Key) được giữ bí mật và áp dụng http://world.std.com/~franl/crypto/one-time-pad.html


+ Nếu 2 "yếu tố" P, K được giữ bí mật absolutely, thì việc với "yếu tố" thứ 3 "C" tìm ra chúng gần như là không thể với cách mã hóa này.

+ Vấn đề mã hóa với Key luôn xoáy sâu vào việc "bảo quản" key. Việc đánh giá nguy hiểm hay không phụ thuộc vào cách bảo quản này.

+ Theo ý kiến riêng của FaL, nói nguy hiểm bởi vì việc giữ K và P trong "thời buổi" hiện nay là việc khó khăn. Chẳng ai bảo đảm được chữ absolute cả.

+ Bác gsmth đưa ra cái này đúng là làm em chột dạ smilie, tiếng Anh nhiều quá, đọc mệt :p!

FaL
Hãy giữ một trái tim nóng và một cái đầu lạnh
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 06/11/2007 12:23:33 (+0700) | #14 | 95622
FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline
[Profile] [PM]
Please delete this entry, it's just a mistake of editing.

FaL
Hãy giữ một trái tim nóng và một cái đầu lạnh
[Up] [Print Copy]
  [Question]   Re: Hỏi về toán tử "^" (XOR) 06/11/2007 12:30:29 (+0700) | #15 | 95625
[Avatar]
alice
Elite Member

[Minus]    0    [Plus]
Joined: 20/01/2005 22:23:24
Messages: 87
Location: Wonderland
Offline
[Profile] [PM]
Giả thiết P được giữ bí mật là không thực tế. Đối thủ có thể đoán biết một phần của P. Thí dụ, nếu P là một bức thư của An gửi cho Bình thì đoạn đầu tiên rất có thể là "Bình mến," và đoạn cuối rất có thể là "Thân, An." smilie

Cho nên tốt hơn là hãy giả thiết đối thủ biết n bit của P, C (n khổng lồ) chỉ còn lại 1 bit không biết.

Để bảo mật bit duy nhất không biết đó, Độn một lần (one-time pad) là cần, nhưng chưa đủ. Còn tùy theo độn với cái gì nữa.

a/ Độn với số ngẫu nhiên K. Biết n bit của K, đối thủ vẫn không thể xác định được bit còn lại: OK, cách này an toàn. Nhưng vì K là số ngẫu nhiên nên không có cách nào tái tạo nó được. Buộc lòng phải lưu trữ và vận chuyển. Để ý độ dài K bằng độ dài P, C, sẽ thấy cách này không thực tế.

b/ Độn với số giả ngẫu nhiên K. Trong đó, K được sinh ra từ khóa Z với độ dài vừa đủ (log(n) chẳng hạn), nhờ một bộ sinh số giả ngẫu nhiên có độ an toàn mật mã (CSPRNG). Cách này thực tế hơn. Nhưng khi đó, sự an toàn tuyệt đối không còn nữa -- từ n bit đã biết của K, đối thủ vẫn có cơ hội tính ngược ra Z hoặc tính luôn bit còn lại của K. An toàn hay không, phụ thuộc vào độ phức tạp của phép tính ngược này.

Các CSPRNG là những hàm phức tạp chứa nhiều phép tính mà XOR (nếu có) chỉ là một. Bên cạnh XOR còn phải dùng những phép tính phi tuyến nữa, không có chúng thì "toi đặc". smilie
Như hà nghịch lỗ lai xâm phạm
如 何 逆 虜 來 侵 犯
[Up] [Print Copy]
[digg] [delicious] [google] [yahoo] [technorati] [reddit] [stumbleupon]
Go to: 
 Users currently in here 
1 Anonymous

Powered by JForum - Extended by HVAOnline
 hvaonline.net  |  hvaforum.net  |  hvazone.net  |  hvanews.net  |  vnhacker.org
1999 - 2013 © v2012|0504|218|