В предвоенные годы японский отдел дешифровальной службы НКВД возглавлял Сергей Семенович Толстой. Одним из самых крупных успехов накануне войны было дешифрование группой специалистов во главе с Толстым японских шифромашин, известных под названиями, данными им американцами: «оранжевая», «красная» и «пурпурная».
В 1935 году криптологи Спецотдела переехали в новое здание по улице Феликса Дзержинского, названной в честь первого председателя ВЧК-ОГПУ. Шифровальный отдел был поделен на несколько отделений, занимавшихся обеспечением секретной связи с региональными управлениями НКВД, пограничными частями и военными формированиями, администрациями тюрем и лагерей, нелегальной зарубежной агентурой и «легальными» резидентурами за рубежом.
За секретную связь с «легальными» резидентурами отвечало 6-е отделение. Его начальник по фамилии Козлов был снят с должности во время репрессий в 1937 году. А после того, как преемник Козлова был отправлен шифровальщиком в США, начальником 6-го отделения стал человек, чье имя приобрело впоследствии скандальную популярность. Это был Владимир Михайлович Петров, который в 1954 году вместе с женой Евдокией получил политическое убежище в Австралии.
В 1933 году, в момент прихода В. М. Петрова в 6-е отделение, оно насчитывало в своем составе 12 человек. Этим людям доверялись самые большие тайны наиболее секретного учреждения в СССР, и поэтому они относились к элите советского общества. Однако их работа была трудной. Операции по дешифровке сообщений выполнялись вручную, и В. М. Петрову часто приходилось задерживаться на работе до полуночи, чтобы успеть вовремя обработать всю массу шифротелеграмм, поступивших к нему в течение дня. Позже, уже будучи заместителем начальника 6-го отделения, В. М. Петров сам уже не занимался шифрованием или дешифровкой, а читал, корректировал и подписывал открытые тексты шифротелеграмм.
Иногда шифровальщикам давались поручения, выходящие далеко за рамки их прямых обязанностей, как это случилось, например, с Яковом Ефимовичем Боковым. Ему было поручено убить советского посла в одной из стран Ближнего Востока, что он и сделал в кабинете последнего, проломив ему череп одним ударом металлического бруска. Чтобы отвести от себя подозрение в убийстве, Я. Е. Боков в течение года продолжал работать шифровальщиком в этом посольстве, а затем вернулся в СССР, где «за успешное выполнение правительственного задания» 14 октября 1939 года был награжден орденом Красной Звезды.
Дешифровальный отдел был разбит на отделения по географическому и языковому принципу — китайское, японское, англо-американское и т. д. Евдокия Петрова (Дуся), которая в течение двух лет изучала японский язык в московской спецшколе, работала в японском отделении. Ее коллегами по работе были: