ความแตกต่างระหว่างการเรียงสับเปลี่ยนและการขนย้ายคืออะไร?

ฉันพยายามที่จะเข้าใจความแตกต่างระหว่างการเรียงสับเปลี่ยนและการขนย้าย ฉันเคยเห็นคำถามที่คล้ายกันในฟอรัม แต่ฉันต้องการขอคำจำกัดความและตัวอย่างที่เหมาะสมจากคุณ ฉันกำลังพยายามทำความเข้าใจอัลกอริทึม DES และฉันต้องการเข้าใจว่าการลดลงครึ่งหนึ่งของบล็อกเริ่มต้นและการสลับครึ่งในท้ายที่สุดจะเป็นการเรียงสับเปลี่ยนหรือการโยกย้าย ขอบคุณล่วงหน้า.

คำตอบนี้มุ่งเน้นไปที่ นิดหน่อย การเรียงสับเปลี่ยนที่ใช้ในบริบทของ เดส สำหรับการเรียงสับเปลี่ยนบิต IP, IP^-1, และ E. เป็นจำนวนบิตที่เริ่มต้นจาก $1$เช่นเดียวกับใน DES

ก การเปลี่ยนแปลงบิต เป็นฟังก์ชัน $g$ ในชุด $\{0,1\}^n$ ของ $n$บิตบิสโทร มันถูกกำหนดโดยเวกเตอร์ของ $n$ จำนวนเต็มที่แตกต่างกัน $p_i$ กับ $1\le p_i\le n$และคุณสมบัติสำหรับบิตสตริงใดๆ $x$ และจำนวนเต็มใดๆ $i$ กับ $1\le ฉัน\le n$หมายเลขบิต $i$ ของภาพบิตสตริง $x$ ตามหน้าที่ $g$ เป็นเลขบิต $p_i$ ของ $x$.

กล่าวอีกนัยหนึ่ง บิตอินพุตแต่ละบิตไปที่บิตเอาต์พุตที่กำหนดโดยเฉพาะ และบิตเอาต์พุต $i$ เป็นบิตอินพุต $p_i$.

การเรียงสับเปลี่ยนทุกบิตคือ a คัดค้าน ในชุด $\{0,1\}^n$. อย่างเท่าเทียมกัน: การเรียงสับเปลี่ยนทุกบิตเป็นการเรียงสับเปลี่ยนของเซตของ $n$บิตบิสโทร มี $n!$ การเรียงสับเปลี่ยนบิตดังกล่าว เทียบกับที่ใหญ่กว่ามาก $(2^น)!$ การเรียงสับเปลี่ยนดังกล่าว ชุดย่อยของการเรียงสับเปลี่ยนบิตถูกปิดภายใต้องค์ประกอบของฟังก์ชัน: การใช้การเรียงสับเปลี่ยนบิตแบบตายตัวใดๆ สองตัวจะทำให้ได้การเรียงสับเปลี่ยนบิต

หมายเหตุ: ผู้เขียนบางคนใช้ การขนย้ายบิต หรือแม้กระทั่ง การขนย้าย เพื่อกำหนดการเรียงสับเปลี่ยนบิตตามที่กำหนดไว้ข้างต้น และแยกความแตกต่างจากการเรียงสับเปลี่ยน นั่นไม่ใช่สิ่งที่ฉันจะทำต่อไปนี้ แต่อาจเป็นสิ่งที่ OP มีอยู่ในใจ

ก การขนย้ายบิต เป็นการสับเปลี่ยนบิตเฉพาะของ $n$-bit bitstrings ซึ่งกำหนดโดยจำนวนเต็มสองจำนวนทั้งหมด $\ell$ และ $ค$ กับ $n=\ell\cdot c$. มันคือ $n$ จำนวนเต็ม $p_i$ เป็น $p_i=1+((i-1)\bmod c)\cdot c+\lfloor (i-1)/c\rfloor$, สำหรับ $1\le ฉัน\le n$.

กล่าวอีกนัยหนึ่งเมื่อเราเขียนบิตอินพุตเป็น $\ell=n/c$ เส้นและ $ค$ คอลัมน์และเอาต์พุตบิตเป็น $ค$ เส้นและ $\ell$ คอลัมน์ คอลัมน์ขาออก $เจ$ มาจากสายป้อน $เจ$.

ตัวอย่างเช่นกับ $\ell=3$ และ $ค=2$การขนย้ายบิตมี $p_1=1$, $p_2=3$, $p_3=5$, $p_4=2$, $p_5=4$, $p_6=6$ซึ่งแสดงได้ดีที่สุดว่าเป็น

     1   3   5
     2   4   6

บางครั้งการเปลี่ยนแปลงบิตด้วย $p_i=\ell\cdot c-((i-1)\bmod c)\cdot c-\lfloor (i-1)/c\rfloor$ ก็ถือเป็นการขนย้ายบิตแบบอื่นเช่นกัน กับ $\ell=3$ และ $ค=2$, การขนย้ายบิตแบบอื่นมี $p_i$

     6   4   2
     5   3   1

เมื่อไร $n$ เป็นรูปสี่เหลี่ยมจัตุรัสและ $\เอล,ค$ ไม่ระบุ สันนิษฐานว่าเป็น $\sqrtn$และทรานสโพซิชันบิตแบบตารางบิตดังกล่าวคือ การมีส่วนร่วม.

การลดลงครึ่งหนึ่งของบล็อกเริ่มต้นและการสลับครึ่งในท้ายที่สุดจะเป็นการเรียงสับเปลี่ยนหรือการโยกย้ายหรือไม่?

ใน เดสการแปลง (ประกอบด้วย IP ตามด้วยการลดจำนวนลงครึ่งหนึ่ง) จากอินพุต 64 บิตเป็น LR เป็นการเปลี่ยนรูปแบบบิต (จึงเป็นการเปลี่ยนรูปของชุด $\{0,1\}^n$แต่มีความเฉพาะเจาะจงน้อยกว่ามาก) มันคือ $p_i$ ได้รับในตาราง IP:

    58  50  42  34  26  18  10   2
    60  52  44  36  28  20  12   4
    62  54  46  38  30  22  14   6
    64  56  48  40  32  24  16   8
    57  49  41  33  25  17   9   1
    59  51  43  35  27  19  11   3
    61  53  45  37  29  21  13   5
    63  55  47  39  31  23  15   7

การแลกเปลี่ยนบรรทัดเป็นประจำทำให้ได้

    64  56  48  40  32  24  16   8
    63  55  47  39  31  23  15   7
    62  54  46  38  30  22  14   6
    61  53  45  37  29  21  13   5
    60  52  44  36  28  20  12   4
    59  51  43  35  27  19  11   3
    58  50  42  34  26  18  10   2
    57  49  41  33  25  17   9   1

ซึ่งเป็นการย้ายบิตตารางสำรองสำหรับ $n=64$. ดังนั้น IP จึงเกือบจะเป็นการย้ายเล็กน้อย

เมื่อถูกมองว่าทำงานบน LR การสลับครึ่งจะเป็นการเปลี่ยนแปลงเล็กน้อย ซึ่ง $p_i$ มอบให้โดย:

    33  34  35  36  37  38  39  40
    41  42  43  44  45  46  47  48
    49  50  51  52  53  54  55  56
    57  58  59  60  61  62  63  64
     1   2   3   4   5   6   7   8
     9  10  11  12  13  14  15  16
    17  18  19  20  21  22  23  24
    25  26  27  28  29  30  31  32

มันไม่ใช่การขนย้ายบิต แต่เป็นการเปลี่ยนรูปแบบบิตปกติมาก (เช่นเดียวกับการขนย้ายบิต) และการมีส่วนร่วม (การขนย้ายบิตแบบสี่เหลี่ยมจัตุรัสคืออะไร)