[Next] [Up/Previous] [Index]

Euler's Constant and the Quadibloc S-Boxes

The initial values of the subkeys and S-boxes in Blowfish are based on pi. To dispel worries about S-boxes with a designed-in weakness in my amateur designs, I have chosen a standard mathematical constant as their source.

The constant I am using is Euler's constant, sometimes called the Euler-Mascheroni constant, also known as gamma. Its value is .57721 56649 01532 86060 65120 90082...

Euler's constant is defined as the limit, as n tends to infinity, of the sum of 1 + 1/2 + 1/3 + ... up to 1/n, minus the natural logarithm of n, normally written:

                      n
                /   ____       \
               |    \      1    |
    lim        |     >    ---   | - ln(n)
n -> infinity  |    /___   i    |
                \    i=1       /
                 

Since

     _n
    /
   |   1
   |  ---, dx = ln(n)
   |   x
 _/
  1

that is, the integral from 1 to n of 1/x with respect to x is the natural logarithm of n, the following diagram illustrates what Euler's constant is in graphical form:

Allowing the graph to continue on indefinitely to the right, the boxes shown which are divided into green and gray areas have a total overall area of 1. (Note that the vertical scale in the graph is exaggerated compared to the horizontal scale for clarity.) Euler's constant, .57721 56649... is the total of the areas of the gray parts of the boxes.

Because only scaling makes the shape of the graph of 1/x from 1 to 2 different from the graph of 1/x from 2 to 4, or the graph of 1/x from 4 to 8, the following diagram:

illustrates a way in which it is possible to derive a formula for Euler's constant that would only involve calculating the natural logarithm of 2.

This formula is:

                                             (i+1)
                     infinity               2
                       ____                 ____
                       \                    \        1     1
gamma = (1 - ln(2)) +   >    (1 - ln(2)) -   >      --- - ---
                       /___                 /___      i    j
                       i = 1                    i    2
                                           j = 2 +1

By superimposing the areas from 1 to 2, from 2 to 4, and 4 to 8 after adjusting them to fit, one sees that another series for Euler's constant, not involving any logarithms, is possible, as it is (1/2 - 1/3) + 2 * ((1/4 - 1/5) + (1/6 - 1/7)) + 3 * ((1/8 - 1/9) + (1/10 - 1/11) + (1/12 - 1/13) + (1/14 - 1/15)) + ..., or, in other words:

                    (i+1)
       infinity    2     - 1
         ____        ____
         \           \          (j-1)   1
gamma =   >     i *   >     (-1)     * ---
         /___        /___               j
         i = 1            i
                     j = 2

Euler's constant is more difficult to calculate than the square root of 2, e, or pi, and it is less well understood. Mathematicians have not yet proven which of rational, algebraic, or transcendental it is.

The S-boxes constructed from Euler's constant (.57721 56649...) for use in the Quadibloc series of block ciphers are derived as follows:

start with an array, A, such that A(0) is 0, A(1) is 1, up to A(255) which is 255. Place Euler's constant to sufficient precision in ACC. Number of choices starts at 256, and is decreased by 1 for each iteration; element to choose starts at 0, and increases by 1 for each iteration. The iteration where Number of choices is 2 is the last iteration.

During each iteration, multiply ACC by Number of choices. Leave the fractional part of the result in ACC; swap

 A( Number of choices )

and

 A( Number of choices + the integer part of the result ).

This generates S-box 1; repeat the procedure with the contents remaining in ACC to obtain S-box 2. (ACC must be long enough to hold Euler's constant to sufficient precision to support both applications of the procedure.)

A BASIC program to generate these S-boxes is given here. And this BASIC program produced the DATA statements it required from a file containing the value of Euler's constant.

Here are the S-boxes thus produced. S-boxes from 1 through 4 are used in several of the ciphers in the Quadibloc series. S-boxes 5 and 6 are combined into one S-box with 512 entries, called S5, in Quadibloc II and III, and similarly S-boxes 7 and 8 become S6 and S-boxes 9 and 10 become S7. S-box 11 is used under the name S9 in Quadibloc III.

S-box 1 is:

 147 196 164  55   9   6  90 236
 192 207  17  58  52 112 227 221
 122  94  60  10 153 245 195 194
  50 135 133 186 183   1 177 132
  48 126 125  12 137 104 105  77
 167  46 228  74 201   5  68 165
   0 204 212 254  97  65  14 113
 134 171  72 151 169  19 211  71
 168 209 238  43  83  84  53 101
 187 214 145 231 172 210  36 175
  76  38   7  79 156 100 222 103
   4  95 217 127 152 198  32 128
  70  96  13 131  41  39 250 205
  91 102  61 241  22  73 247  28
  20 136  33  56  93 108 193 182
 233 213  47  11  16 188 224 240
 106 208   2 140 230  82 166  99
  54 190 243 253 181 255 138 237
 111 219  49 220 143 142 161 162
 251 226 239 180  98 130 107  24
 119  78 146 123  88  45 120 118
  57  21  15 234 150  40  64  35
 154  25  29 139 114  59 144 215
  87  26  37 248  75  86 202 197
  34 163 206  44  69 173  81  92
 216  31 159  62  27 244  30 232
 179  80 218  66 129 148 225 246
 252 170 174   8 200 124  18 203
 191 189 116   3  67 242 229 141
 199 117 121  89 157  42  51 115
  85 160 235 109 158 178 176 223
 249 155 184 185  63 149 110  23

S-box 2 is:

 187  91 192 149 175  80  48 231
  19  23 210  35 104  31  72 111
 180  20  79 100  45 173 240 113
  63 236 201  69 118 181 248 185
 115  62  29 166 253  67  60  41
 247 124 101  24 135  87 221 144
 197 188  93  65 123 142 207 195
 105  53 163 145 190  18 130  76
 233 251 146 161 193 211  10 235
  83  14 174  96  27 151 126 112
  43  34 117 157  56   5 219  22
 155   4 213 186 245  66 214 196
 246  64  49 147  71  61 133  37
  12 227 121  17  68 143 165 176
 191 232   8 116 238  59 184 102
 224 138 170  11  39 205  36 244
 183 140 217 228 237 209 212  42
 177  77 208  78  25 242  15  50
 114  81  97   0 154  13 216   2
 119 152 250  88 220 171 127 103
   1  21  74  70 252 200  92 156
  73  32 226  95 150  99 167 122
 182  84  47 136   3 162 125 139
  98 153 158 134 172 239 168 178
  85 194 249  51 128  33  38 223
 107 254 141 241 148  46 120 198
 137  75 132 108  58 243 225 204
  89 129 131  16 203 255  44  86
 160 189 230 106 215  55 222 229
  94 164  82 202  26 179   6   7
 199  90  30  54  57  40 109  28
 206   9 110  52 218 234 169 159

S-box 3 is:

 169 101  98 166  37 253 215  99
  85 233 210 135 201  79   5 239
  53  11 150 105 141 198 219 234
 195  60 127 143 165  42  64 121
 255  18  78 132 251 159 213 245
 230 106  40 175 153  20  81  23
 212 217 147  74 240 174 171  97
  89  26 187 115  38 220  51 249
  73   7  86  24  82  16 164 250
 179 123 107  49 194 154 204  94
  66 118 231 183  22 113 192 188
 180 167  29 119  46  96 117  28
  35 114 186 197 138 191  52 122
 247  19 103   6  31 102 227 254
 145 246 148  12 156 144 189   8
  61  33  13  58  36 216  41  68
 185  63  69 178 228 172 125 142
  59 243  75 235 202 221  80 151
 120 226  21 155  93  32  25 209
  57   9 168  30 116 252  56 203
 128 146 163 205  95 157 222 177
 244 190 130  17 242  87 161  83
  27 139  44  62  50   4  54  65
 225  72  88   3 232 104 136  10
  48 109 206 218 126 112  43  90
 229 133  14 110 100 162 158 211
 152   2  92 176 199 207   1  84
  34 173 214 170 223  77 184  67
 129 149 182 196  45 200 160  47
 224  39 238 208 124  70 137 193
  15  71 111 237  76 131   0 248
 236 241 181 140  91 108  55 134

S-box 4 is:

  56 185  51  63 131 246  69 102
 177  84  61   1 228 251 219  60
  64 103  34 164   4   0 106  17
 120  53 118 204 127 100  27 231
  93  26 146 133  72 195 240 202
  12 209 236 245 247 149  32 212
  47  70 135 158  79 230  76 223
   9 125  99  31  16 136  77 147
 189  40 188  90 210 159  21  48
  74 145 179 132  14  20  55 243
  24  39 222 134  38  19 232 119
 206 124 168 142 211 171 249  36
  15 121 163 187 161  97 215 203
  71 201  92 113 128 153 181 167
 244 126  58 214 208 250 186 226
 111 162 183 199 140 175 110 213
  50 139 154  94 174  68 207  11
  89 248 166 157  82 115 160  98
 180 221 112 235  25 182 169 194
 116  28   5   8   2 229 176  88
 130  66 192  42  13  86  73  59
 225   7  52  18  57 205 234 237
 178 255 143 218 114  95  29 109
 242  33 129 122 155  35  80 191
 238  67 101 137 138 216 108  85
 253 152   3 123 217 190  96 197
 198 148 200  75  10 233  30  37
  41 227   6 254 252  83  43 220
 104  49 239 196  45  65 172 105
 165  91 150 184  44 173 107  22
  62  46 144 170 117  78 151  87
 141  81  23 156 224 241  54 193

S-box 5 is:

 218  16   5 224 122  22 160 207
  90  43 170 153 221 213 140 178
  93 145  46 135  10  72 229 102
 249  74 254 149 192  45 225 245
  94 105 128 206 114 162  23 233
 117   7  83 169  31 143 109 230
 100  91  34   6 223 240  30 210
  86   2  98 147  77 204 188 106
 103 244 177  27 184 112 191   9
  18  58  68 198 138 251 253  12
 200  42  78 176  20 234 150 144
 116 146   8 164  88  32 222  59
 186 175  47 194 195 141 127  41
 155 255   1  28  24 217 252 165
 154  21 243  92  70 212 139 205
 131 166 196 111 173 123 118 209
 183 125 197 220 126 136  69  26
  48 216  52  85 242 132  35  36
   3 163 219  99  33 211 236  39
 179 187 115 110  56  14  66 142
  79 121 171 108 208  50  60  13
 215  51 181  53 199 167 201 180
 133  84  62 113 157 226  40 159
 239 214  29 119 231  97  81  57
 190 227 168 189  76  11 107 185
  38  25   4  63  71 237 182 151
 137  80 246 232 174 202 134 203
 193  49 250 120 101  96  75 152
  73  64  89 124  44 238 148  65
 247  15  61 158 235  19 156 129
  67  95  54 228   0  87  17 161
 241  37 248 172 130  55 104  82

S-box 6 is:

 237 205  82 124  69  99 132   0
  94   5 244 127 104 115 192  77
 217  63 119 245  61  72 222 118
  75 234  37 167 134  19 243 210
 204  60 195  34 151 229 116 130
  32 176 165 197  38 152  41 180
  20 249  83  31  46 117 103  87
  92  71 108 214 253 144 190 102
  10 129  91   8 160 207 157 223
 232 153 247 159  12  36 163  27
  49 121  79 138  64 219  53 203
  42 200 250 137  47  62 107  23
 246  67  17 248 142 135 139 154
 218  59  68  70 224  97 233  81
  45  24  28  25 202 251 169  74
 184  14  51  85   1 239 255  21
 133 111 120  43 128 215  96   2
 227  35  16  30 122 238 193  40
  84 126  56 150 211  26  50 146
 236 100  44 206 182 158 162  18
  76 252  54 145 125 155 156  73
 186 183  11   6  15   9   3 140
 172 171  48  13 185 164 105 143
  78 228 141  39 213 194  90 209
 230 254 113   4  95 168  55 147
 123  65 175 109  93 196   7 110
 149 212 221 201  57 181 148 216
 166 240 191 136 241 179 170  52
 173 225  98 131 101  33 187 208
 231 242  66 161 189  58 198  86
 178 188 177  80  29 220 235  22
 199  88 174 112 106  89 114 226

S-box 7 is:

 182 195  39 188 242 168 253  54
  47 205  57 244 111 228 245 221
 142  51 237  73 164 190 201 225
  74 227  36 251  41  83   8  70
  79 222  61 189 224 239  97 139
 107 130  48 211 213  55 123 160
 161 162  75 105 175  19 148  30
  42  33  88 219 134 118 143  66
  45  63   0  29 103  67 252 247
 174 159 220 178  92 236  22 132
 231  12 125 170  49 255 155 169
 109  65  56 209   6 181 235 198
 136 131 101 197 233  15 230 117
 241 217 184   7 163 116  31 153
 223 108 194 216 166 114 187 112
  16 102 113 104  27  14  86 229
  87  11 154 183 214 218 106  40
  80  90  64 146 185 119 151 254
  91 100 238 126 243 226 172  77
 191  68  26 145  52   9  23 179
  99  95 206 165 173   4 207 137
 122 176 144  13  17  46   1  98
  96 158  72 127  28 208  18  35
 177  71  60 167 232 249  58 133
  32  78  82 203  25  24  21  69
  10  85  89 196 202 152 147 157
  62 215 246 248  93 210  44 212
  34   5 128 149 110 200 193  76
 250 192  59 199 124  20 138 115
 120  50  53  43 234  84 141 180
 135 204 240 150  94   2   3 121
  38 156 140  37  81 129 171 186

S-box 8 is:

 170  12 142  79  20 169 211 194
  48  41  50  44  67 166 237  62
 107  68  54 175  28 133 190 214
   4 159 108 242  23 207 130 136
  36 119 150 110 168 201 156  85
 183 189 184  11 239  45  60 140
  84  72 249  30 243 158  81  42
  29 202 144  90 241  80 135 111
  94 212  55 160  38  32 164 122
 114  31 224 149 103  97 210 174
 177 227 179 181 165 216 252  82
  14 232 208  34  18  52  57  71
  33 198 217 219  22 121 147  43
 151 228  88 167 132 251  63  78
 236 255  92  86 253   3 100 188
  66 199 235 154 112 248 102  53
  21  77  49 197 233 139   6 105
  83 218  99 186 220 185 254  91
 245 157 176 128 240 178  10  75
   0 129 155  24 238   7 117  51
 120 123 182 143 191 116   8 196
  19 250  27 126  73  39 162 247
  76 141 244 221  35  15  37 204
 234 205 246  58  95 173 206 187
  65 215 172  40  16  69 109 192
 124  56 152  26  46  93 145 148
 118 195 115 203 223 225  64 131
 231 229 134 163 125  98 226 213
 161  17   9  25  87 230 138 153
   2  61   1 137  70  13  89 106
  47 113 222 104 209 200  96 101
  59 171 146  74 193   5 180 127

S-box 9 is:

 143 174  59 186  83  80  63 121
  15  68 182  65 146 189 179  18
 253 219 154  42 135 164  74 196
 136 229 197 161   4 224 120 238
 145 239 103 168 235 245 152  93
  62  46 226  91 173  77  22 109
  94  95 209  87  86 246   8 122
 128 104  64  81 198 236  78  26
   1  99 194 180   0 240 125 204
 144 175  60  14 176  25  31 222
  70 170 167 237 215 142 149 254
  20 181 107  36  41  92  72 166
 126 255 249  52 214 150  40   7
 247 193 234  67  33 210 242  50
 248 250 206 133 102 163 199   2
  84 134 127  49 243 244  96 132
  55 129  39 165 138 117  32  82
 160  47  35 216 148 195 218 225
  66 156 183 101  76  71  24 124
 251  11 153 230  90 211 158 200
  85  98 221 233 241   6  69 227
 190 207  10  61  73 187 157 123
  37 185 100  28 118  16  56 106
  51 188  27 131  13 169  17   9
 139  21 205  88  29 141 231 108
 110 162  54  45 159 111  48 232
 114 155 113 203 140  75 208  97
  79 223 202 115  53 177  30 217
 178 220  38 130 172 192 119 171
   3  43 184 112 105  12 212  57
  58  19 151  89 252 213 228 116
 201  44  34 147 191   5 137  23

S-box 10 is:

  18 230 126 161 150  80 132  11
  40  51  68  43 192   3 233 179
  48 105  33  16 118   6 227  28
 231   8 154 168 181  97 223 221
 188 209  76  64  27 131 210  13
  35 134 164 222 244 145 206 199
 243  10 158 239  15 121 171 238
  34 162 205  84  90   9 234  99
  19 253 207 218   0 178 115 137
 170 196  42 155 212 143 119 148
 106 104  24 177 140 255 144 120
  60  54 110 185  50  91  78 191
 111 159 240  47 160  70  22  39
 215  59 128  65 112 204 186 216
 125 250 195 138 245 247   5  96
  92 242 163  77 141 146  55  83
 167 224  30 153 252 190  46 103
 203 241 208 152 114  52  85  32
 219  74  26 200  14 101  20 117
 193 214 249  95  67  89 135  94
 156 124  72 236 169  56 183 123
 166   2  98 237 172  57 217  61
  41 189 113 194 136 226 248  63
 108  17 180 184  69  44  66 116
  37 175 228 130   4 127  53  49
  71 235  75  29  81 100 109 211
 157  93 246  23 187  86  79  45
 102 149   1 176 198 232 165  73
  62 147 107 142  87  88 225 182
 213  38 197  58  21  82 201 229
  12 151 220 122 129  31 202   7
 133 139  36  25 174 254 251 173

S-box 11 is:

  45 216  52 146 179 234 195  38
 199  56  32  25 229  72 190 163
   2  12 221 242 154 188 113   0
 233 173 251 207 243 231 107   6
  16 184  91  50 162  94  51 230
 205  30 165 210 187  74 129 232
 178 150 177 105  22 156 213 215
 235  14  90 203  59  85 183 139
  70 212  64 247 180 120 218 240
 220  73 110  62  27  39 245  49
 175  79  15 238  40  78  86 111
  98 169  33  17 167 228 181 253
  24  75  61 117 115  35  66 224
 126  19 182 193  31  11  47 109
 136 255 159 138  96  89 160  10
  80 151 121  20 246 143 155 206
  82 171 186 164 114  57 119 161
 102 241 124 249  26   5  71 192
 141 101   9  99 174  84  77 145
 236 131  53 103  88  58 118 127
  48  87 147 223 152 123 132 252
 211 166  29  28  36  13 237 202
  63 122  69   4 217 197 201 148
 254  60 200 208  95  54   7 130
  92 112 222 239   1 204  67 191
 194 248   8 142 157  44  34 189
  41 225 100 176  23  97  93 198
  42 140 116 250 133 106 128 196
  81 104 144 137 125  65  83  37
  18  68 172 135   3  21 214  43
  46 170 219 108 158 244 209 134
 227 226  76 168 185  55 153 149

[Next] [Up/Previous] [Index]

Next
Table of Contents
Main Page